【算法题-困难】按格式合并两个链表

困难算法题，按格式合并两个链表，使用 JavaScript 语言编写

题目

给定两个链表：

• $L_{1} ​= a_{1}​ → a_{2} ​→ ⋯ → a_{n-1} ​→ a_{n}$​
• $L_{2}​ = b_{1}​ → b_{2} ​→ ⋯ → b_{m-1} ​→ b_{m}$​，其中 n ≥ 2m

需要将较短的链表 $L_{2}$ ​反转并合并到较长的链表 $L_{1}$ ​中，使得合并后的链表如下形式：$a_{1}​ → a_{2} ​→ b_{m} ​→ a_{3}​ → a_{4} ​→ b_{m-1} → … $​

合并规则：在长链表中每隔两个元素，将短链表中的元素倒序插入

例如：给定一个较长链表 $1 → 2 → 3 → 4 → 5$ ，另外一个较短链表 6 → 7，需要输出 $1 → 2 → 7 → 3 → 4 → 6 → 5$

输入格式

第一行包含两个链表的第一个节点地址（不确定哪个链表更长），以及两个链表的总节点数 N(≤100000)。节点地址用一个 5 位非负整数表示（可能有前导 0），空地址 NULL 用 −1 表示

例如：00100 01000 7。其中 00100 表示第一个链表的首个节点地址，01000 表示第二个链表的首个节点地址，7 表示两个链表的总节点数。

接下来 N 行，每行描述一个节点的信息，格式为 Address Data Next。其中 Address 是节点地址，Data 是一个绝对值不超过 100000 的整数，Next 是下一个节点的地址。保证两个链表都不为空，且较长的链表至少是较短链表长度的两倍

输出格式

对于每个测试用例，按顺序输出合并后的结果链表。每个结点占一行，按输入的格式输出

输入样例

在这里给出一组输入。例如：

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

输出样例

在这里给出相应的输出。例如：

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

分析

• JavaScript 中没有链表，需要模拟

解答

const inputs = `
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
`;

// 链表类
const nodeAddrMap = new Map();

class Node {
  addr = null
  data = null
  next = null
  constructor(addr, len) {
    len.val += 1;
    this.addr = addr;
    let [data, next] = nodeAddrMap.get(addr);
    this.data = data;
    if (next !== '-1') {
      this.next = new Node(next, len);
    }
  }
  toString() {
    let [next, retV] = [this, []];
    while (next !== null) {
      retV.push(`${next.addr} ${next.data} ${next.next === null ? '-1' : next.next.addr}`);
      next = next.next;
    }
    return retV.join('\n');
  }
  reverse() {
    // 反转链表
    let [prev, current] = [null, this];
    while (current !== null) {
      [current.next, prev, current] = [prev, current, current.next];
    }
    return prev;
  }
}
const c = inputs.split('\n');
const [startAddr1, startAddr2, totalNodeNum] = c[0].split(' ');

for (let i = 1; i <= parseInt(totalNum); i++) {
  let [addr, data, next] = c[i].split(' ');
  nodeAddrMap.set(addr, [data, next]);
}
//构建两个链表并且直接返回链表长度
let len1 = { val: 0 };
let len2 = { val: 0 };
let list1 = new Node(startAddr1, len1);
let list2 = new Node(startAddr2, len2);
if (len1.val < len2.val) {
  // 确保 list1 是长的链表
  [list1, list2] = [list2, list1];
}
// 反转短链表
list2 = list2.reverse();
let [cl1, cl2] = [list1, list2];
while (cl2 !== null) {
  // 长链表每隔2个结点，插一个短链表的结点。直到短链表没有剩余结点
  cl1 = cl1.next;
  [cl1.next, cl2.next, cl2, cl1] = [cl2, cl1.next, cl2.next, cl1.next];
}
console.log('' + list1);