Leetcode 82. Remove Duplicates from Sorted List II

Problem Explanation:

In this problem, we are given a sorted linked list. We have to delete all nodes that contain duplicate numbers and return the modified linked list containing only distinct numbers.

Let's understand this with the help of an example:

Suppose the input linked list is 1->2->2->3->4->4->5.

We see that 2 and 4 are duplicate numbers. After removing all nodes that contain these numbers, our output linked list is 1->3->5.

Approach Explanation:

The solution uses a two-pointer approach and a dummy node.

  1. It starts with creating a dummy node whose next points to the head of the linked list.

  2. The prev pointer points to the dummy node and the head pointer moves along the linked list.

  3. If the current node's value and the next node's value is the same, i.e., a duplicate value is detected, the head pointer moves until a node with a different value is found.

  4. Then we check if the prev pointer's next node is the same as the current head pointer. If it is, this means no duplicate was encountered and we simply move the prev pointer to its next node.

  5. If the prev pointer's next node isn't the same as the current head pointer, this indicates duplicates were encountered and they should be skipped. We do this by setting the prev pointer's next to head's next. We effectively remove the nodes with the duplicate value.

  6. Finally, head pointer moves to the next node. The process continues until the head pointer has visited all nodes.

  7. The modified linked list's head is returned as the final output.

Python Solution:

1
2python 
3class Solution: 
4    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: 
5        # Create a dummy node whose next points to head
6        dummy = ListNode(0, head)
7        prev = dummy
8        
9        while head:
10            # If the current node's value and the next node's value is same
11            # move the head pointer until a node with different 
12            # value is found 
13            while head.next and head.val == head.next.val:
14                head = head.next
15            
16            # Check if prev pointer's next node is the same as 
17            # the current head pointer. If it is, move the prev pointer 
18            # to the next node.
19            if prev.next == head:
20                prev = prev.next
21            
22            # If prev pointer's next node isn't the same as
23            # the current head pointer, we set the prev pointer's next 
24            # to head's next, to skip duplicates nodes
25            else:
26                prev.next = head.next
27                
28            head = head.next
29            
30        return dummy.next 

Similar approach is implemented in other languages too.## JavaScript Solution:

1
2javascript
3var deleteDuplicates = function(head) {
4    // Create a dummy node whose next points to head
5    const dummy = new ListNode();
6    dummy.next = head;
7    let prev = dummy;
8
9    while (head != null) {
10        // If the current node's value and the next node's value is same
11        // move the head pointer until a node with different 
12        // value is found 
13        while (head.next != null && head.val == head.next.val) {
14            head = head.next;
15        }
16
17        // Check if prev pointer's next node is the same as 
18        // the current head pointer. If it is, move the prev pointer 
19        // to the next node.
20        if (prev.next == head) {
21            prev = prev.next;
22        } else {
23            // If prev pointer's next node isn't the same as
24            // the current head pointer, we set the prev pointer's next 
25            // to head's next, to skip duplicates nodes
26            prev.next = head.next;
27        }
28
29        head = head.next;
30    }
31
32    return dummy.next;
33};

Java Solution:

1
2java
3public class Solution {
4    public ListNode deleteDuplicates(ListNode head) {
5        // Create a dummy node whose next points to head
6        ListNode dummy = new ListNode(0);
7        dummy.next = head;
8        ListNode prev = dummy;
9
10        while (head != null) {
11            // If the current node's value and the next node's value is same
12            // move the head pointer until a node with different 
13            // value is found 
14            while (head.next != null && head.val == head.next.val) {
15                head = head.next;
16            }
17
18            // Check if prev pointer's next node is the same as 
19            // the current head pointer. If it is, move the prev pointer 
20            // to the next node.
21            if (prev.next == head) {
22                prev = prev.next;
23            } else {
24                // If prev pointer's next node isn't the same as
25                // the current head pointer, we set the prev pointer's next 
26                // to head's next, to skip duplicates nodes
27                prev.next = head.next;
28            }
29
30            head = head.next;
31        }
32
33        return dummy.next;
34    }
35}

With the help of these solutions, we can now easily delete all the duplicates from a sorted linked list in Python, JavaScript and Java, ensuring to retain only distinct elements in the list. The time complexity for this problem is O(n), where n is the number of nodes in the linked list, and the space complexity is O(1) as we use only a constant amount of space.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫