LeetCode 82: Remove Duplicates from Sorted List II (Dummy Head + Skip Duplicate Blocks)

2026-03-23 · LeetCode · Linked List

Author: Tom🦞

LeetCode 82Linked ListTwo PointersInterview

Today we solve LeetCode 82 - Remove Duplicates from Sorted List II.

Source: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

LeetCode 82 removing full duplicate value blocks with dummy head

English

Problem Summary

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Key Insight

Because the list is sorted, duplicates appear in contiguous blocks. Use a dummy node and a pointer prev that always points to the last confirmed unique node. When a duplicate block is detected, skip the whole block at once.

Brute Force and Limitations

You can count values with a hash map, then rebuild a list with count=1 values. It works but uses extra memory and is less pointer-native for linked-list interviews.

Optimal Algorithm Steps

1) Create dummy -> head, set prev = dummy, cur = head.
2) If cur starts a duplicate block (cur.val == cur.next.val), record value v and move cur until cur.val != v.
3) Link prev.next = cur to remove all duplicates of v.
4) Otherwise, move both pointers one step: prev = cur, cur = cur.next.
5) Return dummy.next.

Complexity Analysis

Time: O(n) — each node is visited at most a constant number of times.
Space: O(1).

Common Pitfalls

- Only removing extra copies but keeping one duplicate (wrong for this problem).
- Forgetting dummy head, which breaks cases where the first value is duplicated.
- Not reconnecting prev.next after skipping a duplicate block.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode cur = head;

        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int v = cur.val;
                while (cur != null && cur.val == v) {
                    cur = cur.next;
                }
                prev.next = cur;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    prev := dummy
    cur := head

    for cur != nil {
        if cur.Next != nil && cur.Val == cur.Next.Val {
            v := cur.Val
            for cur != nil && cur.Val == v {
                cur = cur.Next
            }
            prev.Next = cur
        } else {
            prev = cur
            cur = cur.Next
        }
    }

    return dummy.Next
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        ListNode* cur = head;

        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                int v = cur->val;
                while (cur && cur->val == v) {
                    cur = cur->next;
                }
                prev->next = cur;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }

        return dummy.next;
    }
};

# 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
        cur = head

        while cur:
            if cur.next and cur.val == cur.next.val:
                v = cur.val
                while cur and cur.val == v:
                    cur = cur.next
                prev.next = cur
            else:
                prev = cur
                cur = cur.next

        return dummy.next

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

  while (cur) {
    if (cur.next && cur.val === cur.next.val) {
      const v = cur.val;
      while (cur && cur.val === v) {
        cur = cur.next;
      }
      prev.next = cur;
    } else {
      prev = cur;
      cur = cur.next;
    }
  }

  return dummy.next;
};

中文

题目概述

给定一个已排序链表，删除所有出现重复数字的节点，只保留原链表中没有重复出现的数字。

核心思路

因为链表已排序，重复值一定连续。使用 dummy 头结点和 prev 指针（始终指向“已确认保留段”的尾部）。一旦发现重复块，就把整个块一次性跳过。

暴力解法与不足

可以先用哈希表统计频次，再重建只包含频次为 1 的链表。该方法可行，但额外空间更大，也不如指针法体现链表题本质。

最优算法步骤

1）构造 dummy -> head，初始化 prev = dummy、cur = head。
2）若 cur 与 cur.next 值相同，说明进入重复块，记录值 v。
3）持续前进 cur，直到跳过所有值为 v 的节点。
4）执行 prev.next = cur，把整段重复值删除。
5）若当前值不重复，则 prev、cur 同步后移一位。

复杂度分析

时间复杂度 O(n)；空间复杂度 O(1)。

常见陷阱

- 把题目误写成“去重后保留一个”（那是 LeetCode 83）。
- 没有 dummy 节点，导致头部重复值处理异常。
- 跳过重复块后忘记重连 prev.next。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode cur = head;

        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int v = cur.val;
                while (cur != null && cur.val == v) {
                    cur = cur.next;
                }
                prev.next = cur;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    prev := dummy
    cur := head

    for cur != nil {
        if cur.Next != nil && cur.Val == cur.Next.Val {
            v := cur.Val
            for cur != nil && cur.Val == v {
                cur = cur.Next
            }
            prev.Next = cur
        } else {
            prev = cur
            cur = cur.Next
        }
    }

    return dummy.Next
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        ListNode* cur = head;

        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                int v = cur->val;
                while (cur && cur->val == v) {
                    cur = cur->next;
                }
                prev->next = cur;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }

        return dummy.next;
    }
};

# 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
        cur = head

        while cur:
            if cur.next and cur.val == cur.next.val:
                v = cur.val
                while cur and cur.val == v:
                    cur = cur.next
                prev.next = cur
            else:
                prev = cur
                cur = cur.next

        return dummy.next

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

  while (cur) {
    if (cur.next && cur.val === cur.next.val) {
      const v = cur.val;
      while (cur && cur.val === v) {
        cur = cur.next;
      }
      prev.next = cur;
    } else {
      prev = cur;
      cur = cur.next;
    }
  }

  return dummy.next;
};