Medium

题目描述

给定一个已排序的链表的头 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
  • 题目数据保证链表已经按升序排列

解题思路

解题思路

这道题要求删除所有重复的节点，而不是仅保留一个重复节点，这与普通的去重有所不同。

核心思路：

  1. 使用哑节点（dummy node）简化边界处理，避免头节点被删除的复杂情况
  2. 维护两个指针：prev 指向上一个确定保留的节点，curr 用于遍历
  3. 当发现重复元素时，记录重复值，然后跳过所有具有该值的节点
  4. 只有当节点值唯一时，才将其连接到结果链表中

算法流程：

  • 创建哑节点作为新链表的头部
  • 遍历原链表，检查当前节点是否与下一节点值相同
  • 如果相同，记录该值并跳过所有相同值的节点
  • 如果不同，将当前节点连接到结果链表
  • 最终返回哑节点的下一个节点

这种方法能够一次遍历完成去重，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        ListNode* curr = head;
        
        while (curr) {
            if (curr->next && curr->val == curr->next->val) {
                int duplicateVal = curr->val;
                while (curr && curr->val == duplicateVal) {
                    curr = curr->next;
                }
                prev->next = curr;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }
        
        return dummy->next;
    }
};

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        curr = head
        
        while curr:
            if curr.next and curr.val == curr.next.val:
                duplicate_val = curr.val
                while curr and curr.val == duplicate_val:
                    curr = curr.next
                prev.next = curr
            else:
                prev = curr
                curr = curr.next
        
        return dummy.next

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null) {
            if (curr.next != null && curr.val == curr.next.val) {
                int duplicateVal = curr.val;
                while (curr != null && curr.val == duplicateVal) {
                    curr = curr.next;
                }
                prev.next = curr;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        
        return dummy.next;
    }
}

var deleteDuplicates = function(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let curr = head;
    
    while (curr) {
        if (curr.next && curr.val === curr.next.val) {
            let val = curr.val;
            while (curr && curr.val === val) {
                curr = curr.next;
            }
            prev.next = curr;
        } else {
            prev = curr;
            curr = curr.next;
        }
    }
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历链表一次，n为链表节点数
空间复杂度O(1)只使用常数个额外指针变量

相关题目