82. Remove Duplicates from Sorted List II

Problem Description

In this problem, we are given the head of a linked list that is already sorted. Our task is to delete all nodes that have duplicate numbers, leaving only those numbers that appear exactly once in the original list. It is important to note that the returned linked list must be sorted as well, which is naturally maintained as we only remove duplicates from the already sorted list. For example, given 1->2->3->3->4->4->5, the output should be 1->2->5 since 3 and 4 are duplicates and should be removed.

Intuition

To solve this problem, we aim to traverse the linked list and remove all the duplicates. One common approach to solve such problems is to use a two-pointer technique where one pointer is used to keep track of the current node of interest ('cur') and another to track the node before the current 'group' of duplicates ('pre').

By iterating through the linked list, we move the 'cur' pointer whenever we find that the current node has the same value as the next node (i.e., a duplicate). Once we're past any duplicates, we check if 'pre.next' is equal to 'cur', which would mean that 'cur' has no duplicates. If that's the case, we move 'pre' to 'cur'; otherwise, we set 'pre.next' to 'cur.next', effectively removing the duplicate nodes from the list.

This way, we traverse the list only once and maintain the sorted order of the non-duplicate elements. The use of a dummy node (which 'pre' points to initially) makes sure we also handle the case where the first element(s) of the list are duplicates and need to be removed.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation of the solution follows a simple yet effective approach to eliminate duplicates from a sorted linked list:

Initialization: We initialize a dummy node that points to the head of the list. This dummy node acts as a placeholder for the start of our new list without duplicates. We also create two pointers, pre and cur.
- pre is initially set to the dummy node. It will eventually point to the last node in the list that has no duplicates.
- cur is set to the head of the list and is used to iterate through and identify duplicates.
Iteration: We use a while loop to iterate over the list with the cur pointer until we reach the end of the list. Within this loop:
- We use another while loop to skip all the consecutive nodes with the same value. This is done by checking if cur.next exists and if cur.next.val is the same as cur.val. If so, we move cur to cur.next.
- After skipping all nodes with the same value, we check whether pre.next is the same as cur. If it is, this means cur is distinct, and thus we simply move pre to be cur. If not, it means we have skipped some duplicates, so we remove them by linking pre.next to cur.next.
Link Adjustment: If duplicates were removed, pre.next is assigned to cur.next. This effectively removes all the duplicates we have just skipped over because we link the last non-duplicate node to the node right after the last duplicate node.
Move to Next Node: We move cur to cur.next to proceed with the next group of nodes.
Result: After the loop finishes, dummy.next points to the head of the final list with all duplicates removed. Since we maintained the relative order of the non-duplicate elements and the list was initially sorted, the result is a sorted linked list with all duplicates removed.

By following this approach, using a dummy node, two pointers, and careful link adjustments as we iterate through the list, we ensure:

The original sorted order of the list is preserved.
All duplicates are removed in one pass, making the solution efficient.

The solution exploits the sorted property of the input list, allowing us to detect duplicates easily by comparing adjacent nodes. The use of a dummy node allows for a uniform deletion process, including the edge case where the head of the list contains duplicates and must be deleted.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the sorted linked list: 1->2->2->3.

Initialization:
- Create a dummy node. Let's say dummy.val is 0, and dummy.next points to the head of our list, so now we have 0->1->2->2->3.
- Set the pre pointer to dummy and cur pointer to head (which is 1).
Iteration:
- The list is now 0->1->2->2->3 with pre at 0 and cur at 1.
- cur.next is 2. Since cur.val is not equal to cur.next.val, we move pre to cur, and cur to cur.next.
- Now pre is at 1 and cur is at the first 2.
Identifying Duplicates:
- cur.next is also 2. Since cur.val equals cur.next.val, we move cur to cur.next. Now, cur is at the second 2.
- After the inner loop, cur.next is 3, which is not equal to cur.val. Since pre.next (which is the first 2) is not equal to cur (which is the second 2), we found duplicates.
Link Adjustment:
- We link pre.next to cur.next, effectively removing both 2s. The list now becomes 0->1->3.
Move to Next Node:
- Move cur to cur.next, which is 3.
- cur.next is null now, ending the iteration.
Result:
- The final list is pointed to by dummy.next, which is 1->3, with all duplicates (2->2) removed.

By applying this approach, we have effectively removed all nodes with duplicate numbers from our sorted linked list by only traversing the list once, and the sorted property of the list remained intact.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next_node=None):
4        self.val = val
5        self.next = next_node
6
7class Solution:
8    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        # Create a dummy node which acts as the new head of the list
10        dummy = prev_node = ListNode(next_node=head)
11      
12        # Initialize the current pointer to the head of the list
13        current = head
14      
15        # Iterate through the list
16        while current:
17            # Skip all duplicate nodes
18            while current.next and current.next.val == current.val:
19                current = current.next
20          
21            # Check if duplicates were found
22            # If prev_node.next is the same as current, no duplicates were immediately following
23            # If not, duplicates were found and they are skipped
24            if prev_node.next == current:
25                prev_node = current
26            else:
27                prev_node.next = current.next
28          
29            # Move to the next node in the list
30            current = current.next
31      
32        # After filtering duplicates, return the next node of dummy since it stands before the new head of list
33        return dummy.next
34

1class Solution {
2    public ListNode deleteDuplicates(ListNode head) {
3        // Dummy node to act as a fake head of the list
4        ListNode dummyNode = new ListNode(0, head);
5      
6        // This pointer will lag behind the current pointer and point to the last
7        // node of the processed list without duplicates
8        ListNode precedingNode = dummyNode;
9      
10        // This pointer will traverse the original list
11        ListNode currentNode = head;
12      
13        // Iterate through the list
14        while (currentNode != null) {
15            // Skip all nodes that have the same value as the current node
16            while (currentNode.next != null && currentNode.next.val == currentNode.val) {
17                currentNode = currentNode.next;
18            }
19          
20            // If there are no duplicates for the current value,
21            // then the precedingNode should now point to the currentNode
22            if (precedingNode.next == currentNode) {
23                precedingNode = currentNode;
24            } else {
25                // Otherwise, bypass all duplicates by linking precedingNode to the node
26                // following the last duplicate
27                precedingNode.next = currentNode.next;
28            }
29            // Move to the next node in the list
30            currentNode = currentNode.next;
31        }
32      
33        // Return the processed list without duplicates
34        return dummyNode.next;
35    }
36}
37

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* deleteDuplicates(ListNode* head) {
14        // Create a dummy node that points to the head of the list
15        ListNode* dummyNode = new ListNode(0, head);
16        ListNode* pred = dummyNode; // Predecessor node that trails behind the current node
17        ListNode* curr = head; // Current node we're examining
18
19        // Traverse the list
20        while (curr) {
21            // Skip duplicate nodes
22            while (curr->next && curr->next->val == curr->val) {
23                curr = curr->next;
24            }
25            // If the predecessor's next is the current node, no duplicates were found
26            // Move the predecessor to the current node
27            if (pred->next == curr) {
28                pred = curr;
29            } else {
30                // Skip the duplicate nodes by linking the predecessor's next to the current's next
31                pred->next = curr->next;
32            }
33            // Move to the next node
34            curr = curr->next;
35        }
36        // Return the modified list, excluding the dummy node
37        return dummyNode->next;
38    }
39};
40

1// Type definition for ListNode
2type ListNode = {
3  val: number;
4  next: ListNode | null;
5};
6
7// Function to create a new ListNode
8const createListNode = (val: number, next: ListNode | null = null): ListNode => {
9  return { val, next };
10};
11
12/**
13 * Deletes all duplicates such that each element appears only once
14 *
15 * @param {ListNode | null} head - The head of the input linked list
16 * @return {ListNode | null} The modified list with duplicates removed
17 */
18const deleteDuplicates = (head: ListNode | null): ListNode | null => {
19  // Create a dummy head to ease the deletion process by avoiding edge cases at the list start
20  const dummy: ListNode = createListNode(0, head);
21
22  // Pointers for the previous and current nodes, starting with dummy and head
23  let previous: ListNode = dummy;
24  let current: ListNode | null = head;
25
26  // Iterate through the list
27  while (current) {
28    // Skip all nodes that have the same value as the current node
29    while (current.next && current.val === current.next.val) {
30      current = current.next;
31    }
32
33    // If the next node of previous is current, we did not find duplicates
34    // Move pre to cur
35    if (previous.next === current) {
36      previous = current;
37    } else {
38      // If there were duplicates, skip them by pointing pre.next to cur.next
39      previous.next = current.next;
40    }
41
42    // Move to the next node
43    current = current.next;
44  }
45
46  // Return the modified list without the initial dummy node
47  return dummy.next;
48};
49
50// Note: To execute this code, a ListNode type declaration as well as createListNode()
51// function must exist in the global scope. The deleteDuplicates() function will also
52// be globally accessible.
53

Time and Space Complexity

The time complexity of the provided code to delete duplicates in a sorted linked list is O(n), where n is the number of nodes in the linked list. This is because the code iterates through each node exactly once, and while there can be inner loops to skip duplicate values, each node is visited only once due to the fact that the code moves the pointer cur forward to skip all duplicates of the current node in one go.

The space complexity of the code is O(1). It uses a fixed amount of extra space: the dummy and pre variables, which do not depend on the size of the input linked list. No additional data structures are utilized that would scale with the input size, hence the constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know