LeetCode 82. 删除排序链表中的重复元素 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：哨兵节点 + 单指针（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 82. 删除排序链表中的重复元素 II

思路分析

解法一：哨兵节点 + 单指针（推荐）

核心思路：

引入哨兵节点 dummy（值任意），令 cur = dummy，利用「当前节点的下两个节点」判断是否出现重复：

若 cur.next.val == cur.next.next.val：出现重复，记录重复值，用内层循环跳过所有相同节点，将 cur.next 直接指向第一个不同值节点

否则：cur.next 无重复，安全前进 cur = cur.next

关键细节：外层循环条件 cur.next != null && cur.next.next != null，确保比较两个节点时不越界。

举例：1 → 2 → 3 → 3 → 4 → 4 → 5

cur 在 dummy：发现 1 不重复，cur 前进到 1

cur 在 1：发现 2 不重复，cur 前进到 2

cur 在 2：发现 3 重复，跳过所有 3，cur.next 指向 4

cur 在 2：发现 4 重复，跳过所有 4，cur.next 指向 5

cur 在 2：cur.next.next == null，退出循环

结果：1 → 2 → 5

复杂度分析：

时间复杂度：O(n)，其中 n 为链表节点数，每个节点最多访问两次

空间复杂度：O(1)，仅使用常数额外空间

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                // 记录重复值，跳过所有相同节点
                int val = cur.next.val;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy
	for cur.Next != nil && cur.Next.Next != nil {
		if cur.Next.Val == cur.Next.Next.Val {
			// 记录重复值，跳过所有相同节点
			val := cur.Next.Val
			for cur.Next != nil && cur.Next.Val == val {
				cur.Next = cur.Next.Next
			}
		} else {
			cur = cur.Next
		}
	}
	return dummy.Next
}

解法二：递归

核心思路：

递归地处理链表，使每一层仅关注当前节点与下一节点是否重复。

若 head.val == head.next.val，跳过所有相同值节点，对第一个不同节点继续递归。

否则保留当前节点，递归处理 head.next 并接回结果。

复杂度分析：

时间复杂度：O(n)，其中 n 为链表节点数，每个节点最多访问一次。

空间复杂度：O(n)，递归调用栈最坏为 n。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        if (head.val == head.next.val) {
            // 跳过所有重复值节点
            int val = head.val;
            while (head != null && head.val == val) {
                head = head.next;
            }
            return deleteDuplicates(head);
        }

        // 保留当前节点，递归处理后续部分
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	if head.Val == head.Next.Val {
		// 跳过所有重复的节点
		for head.Next != nil && head.Val == head.Next.Val {
			head = head.Next
		}
		return deleteDuplicates(head.Next)
	}
	head.Next = deleteDuplicates(head.Next)
	return head
}

相似题目

题目	难度	考察点
83. 删除排序链表中的重复元素	简单	链表去重（保留一个）
26. 删除有序数组中的重复项	简单	数组去重双指针
80. 删除有序数组中的重复项 II	中等	数组去重最多保留两个
203. 移除链表元素	简单	链表节点删除
19. 删除链表的倒数第 N 个结点	中等	链表节点删除+双指针
27. 移除元素	简单	原地移除指定值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/62704507