合并两个有序链表（保留重复与去重两版）

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

问题一:合并两个有序链表(LeetCode 21,保留重复)

将两个升序链表 l1、l2 合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,3,5], l2 = [2,4,6]
输出：[1,2,3,4,5,6]

问题二:合并的同时删除重复节点

在合并的基础上,若最终链表中出现值相同的相邻节点,只保留一个。

输入：l1 = [1,2,3], l2 = [2,3,4]
输出：[1,2,3,4]      // 去重后
对比（不去重）：      [1,2,2,3,3,4]

两版共享同一内核:每次从两条链表的表头挑较小者接到结果尾部。去重版只是在"接入前"多问一句:这个值和结果链表的末尾是否相同?相同就跳过。

思路拆解

暴力解法:全部倒进数组,排序后重建

最直觉的想法:遍历两条链表把所有值塞进一个数组,sort 排序,再建成新链表。

点击展开暴力解法（不推荐）

// 收集所有值 → 排序 → 重建链表
function mergeTwoLists(l1, l2) {
  const vals = [];
  for (const head of [l1, l2]) {
    let node = head;
    while (node) { vals.push(node.val); node = node.next; }
  }
  vals.sort((a, b) => a - b); // 丢掉了「已有序」这个宝贵前提

  const dummy = new ListNode(0);
  let cur = dummy;
  for (const v of vals) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }
  return dummy.next;
}

为什么暴力解法不好？

两条链表本身已经有序,这是极其宝贵的前提。暴力法却把它们打散重排,sort 带来 的时间开销,还额外用了 数组。我们完全可以利用有序性,用双指针一趟 线性合并。

最优解法:双指针 + 哑节点(问题一)

这正是归并排序"合并"步骤的核心。维护两个指针 l1、l2 分别指向两条链表当前最小的未处理节点,每次比较,把较小者接到结果链表尾部并前移该指针。

核心思路

1. 建哑节点 dummy,让游标 cur 从它出发,免去"结果链表头为空"的特判;
2. 当 l1 与 l2 都非空时,比较 l1.val 与 l2.val,把较小者接到 cur.next,并前移对应指针与 cur;
3. 循环结束后,必有一条链表已走完,另一条剩余部分整体有序,直接把 cur.next 指向那条非空链表即可(无需逐个搬运);
4. 返回 dummy.next。

关键在于利用了两个前提:各自内部有序 + 每次取全局最小。用不变量描述:每一步接入的值都 结果链表当前末尾的值,故结果始终有序。

去重版:接入前先比对结果末尾(问题二)

去重的关键判断

在把候选节点接到 cur.next 之前,先看它的值是否等于 cur 当前的值(即结果链表的末尾)。若相等则跳过(不接入,只前移源指针);否则正常接入。用一句话:

由于两条输入链表各自有序、合并过程也按非降序接入,所有相等的值必然相邻,因此只需和"末尾一个"比较即可完成全局去重。

递归写法（问题一，思路简洁）

// 谁小谁当头，剩下的交给递归
function mergeTwoLists(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

交互式动画演示

下面用样例 l1 = [1,3,5]、l2 = [2,4,6] 演示双指针合并的完整过程。点击 下一步 观察 l1、l2 指针的比较与结果链表的逐步构建:

步骤 1 / 8

l1

l1 1

→

3

→

5

→

null

 

l2

l2 2

→

4

→

6

→

null

结果

D

→（空）

初始化：建立哑节点 dummy，l1 指向 1，l2 指向 2，结果链表为空。每轮比较两指针，取较小者接到结果尾部。

完整代码(JavaScript)

问题一:合并(保留重复)

高亮行为比较与接入的核心。

/**
 * @param {ListNode} l1  升序链表一
 * @param {ListNode} l2  升序链表二
 * @return {ListNode}    合并后的升序链表
 */
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0); // 哑节点，简化头处理
  let cur = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) { // 取较小者接入
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next; // 结果游标后移
  }

  // 必有一条已空，把剩下那条整体接上
  cur.next = l1 !== null ? l1 : l2;

  return dummy.next;
}

问题二:合并 + 去重

高亮行为去重判断的核心。

/**
 * 合并两个有序链表并删除重复值，只保留每个值的一个副本
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function mergeAndDedup(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;

  while (l1 && l2) {
    // 选出较小者作为候选，但先不移动 cur
    let pick;
    if (l1.val <= l2.val) { pick = l1; l1 = l1.next; }
    else                  { pick = l2; l2 = l2.next; }

    // 仅当与结果末尾不同才接入（cur === dummy 时末尾视为"无值"）
    if (cur === dummy || cur.val !== pick.val) {
      cur.next = pick;
      cur = cur.next;
    }
    // 否则跳过 pick（它是重复值）
  }

  // 处理剩余链表，同样要去重
  let rest = l1 !== null ? l1 : l2;
  while (rest) {
    if (cur === dummy || cur.val !== rest.val) {
      cur.next = rest;
      cur = cur.next;
    }
    rest = rest.next;
  }
  cur.next = null; // 断开尾部，防止残留重复节点的旧指向

  return dummy.next;
}

去重版为何要 cur.next = null？

因为去重时我们可能"跳过"某些节点,cur 最终停留的节点其原始 next 可能仍指向被跳过的重复节点。若不显式断尾,结果链表末尾可能挂上多余节点。接完剩余后务必把 cur.next 置 null。

复杂度分析

设两条链表长度分别为 、。

解法	时间复杂度	空间复杂度	说明
暴力(数组+排序)			丢弃了有序性,还额外建数组
双指针合并(问题一)			一趟线性,复用原节点不新建
递归合并			递归栈深度为
双指针合并+去重(问题二)			仅多一次值比较,复杂度不变

边界与易错点

常见踩坑

1. 忘记接剩余链表:while (l1 && l2) 结束后必有一条非空,漏掉 cur.next = l1 ?? l2 会丢失后半段。
2. 不用哑节点:结果链表头为空时的特判极易写错,哑节点让 cur 永远有落脚点,最后返回 dummy.next。
3. 稳定性 / 相等时的选择:用 l1.val <= l2.val(带等号)可保证相等时优先取 l1,合并是稳定的;写成 < 也对,但去重版建议明确一致。
4. 去重版忘记断尾:见上方 warning,cur.next = null 不可省。
5. 去重版对"剩余链表"也要去重:剩余段虽自身有序,但它的第一个值可能与结果末尾相同,不能直接整体接上,必须继续逐个判断。
6. 空链表输入:任一或两条为 null 时,双指针写法天然覆盖(循环不进入,直接接非空那条或返回 null)。

一句话总结

双指针 + 哑节点,每次取较小者接入,循环后接上剩余段。 去重版只需在接入前比对结果末尾、跳过相等值,并记得最后断尾。核心是善用"两表各自有序"这个前提。