What is the main pattern to solve Remove Duplicates from Sorted List II?

The main pattern involves linked list pointer manipulation, where you use two pointers to identify and skip duplicate nodes.

How do I efficiently remove duplicates from a sorted linked list?

Use two pointers to traverse the list, keeping track of duplicates and skipping over them, modifying the list in-place to ensure sorted order.

What is the time complexity of the optimal solution?

The time complexity is O(n), where n is the number of nodes, as each node is processed once.

How should edge cases, like an empty list or all duplicates, be handled?

For an empty list, simply return null. For all duplicates, ensure that the solution correctly identifies and removes the duplicate nodes, leaving the list empty or with distinct values only.

Can I use a hash set to solve this problem?

Using a hash set could solve the problem but at the cost of additional space complexity. The optimal solution uses constant space.

#82

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

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

给定一个已排序的链表的头 head ，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。示例 1：输入： head = [1,2,3,3,4,4,5] 输出： [1,2,5] 示例 2：输入： head = [1,1,1,2,3] 输出： [2,3] 提示：链表中…

链表双指针

题目描述

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

lightbulb

解题思路

方法一：一次遍历

我们先创建一个虚拟头节点 $dummy$ ，令 $dummy.next = head$ ，然后创建指针 $pre$ 指向 $dummy$ ，指针 $cur$ 指向 $head$ ，开始遍历链表。

当 $cur$ 指向的节点值与 $cur.next$ 指向的节点值相同时，我们就让 $cur$ 不断向后移动，直到 $cur$ 指向的节点值与 $cur.next$ 指向的节点值不相同时，停止移动。此时，我们判断 $pre.next$ 是否等于 $cur$ ，如果相等，说明 $pre$ 与 $cur$ 之间没有重复节点，我们就让 $pre$ 移动到 $cur$ 的位置；否则，说明 $pre$ 与 $cur$ 之间有重复节点，我们就让 $pre.next$ 指向 $cur.next$ 。然后让 $cur$ 继续向后移动。继续上述操作，直到 $cur$ 为空，遍历结束。

最后，返回 $dummy.next$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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 = pre = ListNode(next=head)
        cur = head
        while cur:
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            if pre.next == cur:
                pre = cur
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy.next

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate correctly apply linked list pointer manipulation?
question_mark
How does the candidate handle edge cases, such as empty or duplicate-only lists?
question_mark
Is the solution optimal in terms of both time and space complexity?

warning

常见陷阱

外企场景

error
Overcomplicating the problem with additional data structures.
error
Not correctly linking the predecessor node when skipping duplicates.
error
Failing to handle edge cases such as empty lists or all duplicates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution recursively instead of iteratively.
arrow_right_alt
Using a hash set to track duplicates (though this adds extra space complexity).
arrow_right_alt
Modifying the list in-place without using extra pointers.

help

常见问题

外企场景

继续练习

#86 分隔链表 #61 旋转链表 #141 环形链表