LeetCode 删除排序链表中的重复元素题解

题目

删除排序链表中的重复元素

给定一个已排序的链表的头 head， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。

解题思路

• 因为链表是有序的，所以重复元素一定相邻
• 遍历链表，如果发现当前元素和下个元素值相等，就删除下个元素值

「已排序」这个前提是这道题能做得这么简单的全部原因。相同的值必然挨在一起，所以只需要比较相邻两个节点，不需要任何额外的数据结构来记录见过哪些值。如果链表无序，就得用 Set 存已出现的值，空间从 O(1) 涨到 O(n)。

删除的动作就是改指针：把当前节点的 next 跨过重复的那个，直接指向再下一个。被跳过的节点不再被任何节点引用，JS 的垃圾回收会处理掉它，不用手动释放。

这里有个容易写错的地方：删除之后当前指针不能往前走。因为可能存在连续多个重复值，比如 1 -> 1 -> 1，跳过一个之后新的下一个可能还是重复的，必须停在原地继续比。只有在两个值不同的时候才前进。所以循环里是 if 和 else 二选一，不能两件事都做。

题解

var deleteDuplicates = function (head) {
  let p1 = head;

  while (p1 && p1.next) {
    if (p1.val === p1.next.val) {
      p1.next = p1.next.next;
    } else {
      p1 = p1.next;
    }
  }
  return head;
};

循环条件 p1 && p1.next 两个都得判。p1 非空处理空链表的情况，p1.next 非空保证有下一个节点可以比较——走到最后一个节点时就该停了，不判断的话 p1.next.val 会在 null 上取属性而报错。

直接返回 head 是因为头节点一定会保留。这道题要求每个值留一个，而重复元素相邻，所以第一个节点必然是它那组值的代表，不会被删掉。这一点让代码省掉了哑节点。

对比一下会更清楚：如果题目改成「删除所有含有重复数字的节点，只保留没重复过的」（也就是第 82 题），头节点本身就可能被整组删掉，这时候就必须引入哑节点顶在前面，否则新头节点没法表达。哑节点用不用，取决于头节点会不会被删。

复杂度上，时间是 O(n)，指针总共只往前走一趟。空间是 O(1)，只用了一个指针变量，属于原地修改。