0082. 删除排序链表中的重复元素 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哨兵节点 + 双指针

1. 📝 题目描述

• leetcode

给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回 已排序的链表。

---

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

---

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

---

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

2. 🎯 s.1 - 哨兵节点 + 双指针

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode dummy = {0, head};
    struct ListNode* prev = &dummy;

    while (prev->next) {
        struct ListNode* cur = prev->next;
        // 跳过所有重复节点
        while (cur->next && cur->val == cur->next->val)
            cur = cur->next;
        if (prev->next == cur) {
            prev = prev->next; // 无重复，前进
        } else {
            prev->next = cur->next; // 跳过所有重复节点
        }
    }
    return dummy.next;
}

js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  const dummy = new ListNode(0, head)
  let prev = dummy

  while (prev.next) {
    let cur = prev.next
    // 跳过所有重复节点
    while (cur.next && cur.val === cur.next.val) cur = cur.next
    if (prev.next === cur) {
      prev = prev.next // 无重复，前进
    } else {
      prev.next = cur.next // 跳过所有重复节点
    }
  }
  return dummy.next
}

py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy

        while prev.next:
            cur = prev.next
            # 跳过所有重复节点
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
            if prev.next is cur:
                prev = prev.next  # 无重复，前进
            else:
                prev.next = cur.next  # 跳过所有重复节点
        return dummy.next

• 时间复杂度：$O(n)$，其中 n 是链表长度，每个节点最多访问一次
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 创建哨兵节点 dummy 指向 head，用 prev 指向最后一个确认不重复的节点
• 从 prev.next 出发，用 cur 向后扫描跳过所有相同值的节点
• 若 prev.next == cur 说明无重复，prev 前进；否则 prev.next = cur.next 删除所有重复节点