#82

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Remove Duplicates from Sorted List II

Remove duplicates from a sorted linked list, leaving only distinct values, and return the modified list in sorted order.

linked list two pointers

Problem Statement

Given the head of a sorted linked list, your task is to remove all nodes that have duplicate numbers, ensuring that only distinct values remain. The modified list should be returned in sorted order.

For example, if the input list is [1,2,3,3,4,4,5], the output should be [1,2,5], as the duplicates '3' and '4' are removed.

Examples

Example 1

Input: head = [1,2,3,3,4,4,5]

Output: [1,2,5]

Example details omitted.

Example 2

Input: head = [1,1,1,2,3]

Output: [2,3]

Example details omitted.

Constraints

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

Solution Approach

Pointer Traversal with Two Pointers

Use two pointers to traverse the list. One pointer tracks the current node, and the second identifies duplicate sequences. Remove nodes that are part of duplicate groups and ensure the result maintains sorted order.

Predecessor Node Tracking

Track the predecessor node to link it to the first distinct node when duplicates are found. This allows skipping over all duplicate nodes efficiently.

Edge Case Handling

Handle cases where the list has zero nodes or consists entirely of duplicates. These cases require specific checks to avoid unnecessary operations and ensure correct output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of nodes in the linked list, as each node is processed once. The space complexity is O(1), as no additional data structures are used, and the list is modified in-place.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Single Pass

First, we create a dummy head node $dummy$, and set $dummy.next = head$. Then we create a pointer $pre$ pointing to $dummy$, and a pointer $cur$ pointing to $head$, and start traversing the linked list.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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

Continue Practicing

#86 partition list #61 rotate list #141 linked list cycle