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.
-
It starts with creating a dummy node whose next points to the head of the linked list.
-
The
prev
pointer points to the dummy node and thehead
pointer moves along the linked list. -
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.
-
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 theprev
pointer to its next node. -
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 theprev
pointer's next tohead
's next. We effectively remove the nodes with the duplicate value. -
Finally,
head
pointer moves to the next node. The process continues until thehead
pointer has visited all nodes. -
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.