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
andcur
.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 thecur
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 ifcur.next
exists and ifcur.next.val
is the same ascur.val
. If so, we movecur
tocur.next
. - After skipping all nodes with the same value, we check whether
pre.next
is the same ascur
. If it is, this meanscur
is distinct, and thus we simply movepre
to becur
. If not, it means we have skipped some duplicates, so we remove them by linkingpre.next
tocur.next
.
- We use another
-
Link Adjustment: If duplicates were removed,
pre.next
is assigned tocur.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
tocur.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 EvaluatorExample 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
is0
, anddummy.next
points to the head of our list, so now we have0->1->2->2->3
. - Set the
pre
pointer todummy
andcur
pointer tohead
(which is1
).
- Create a dummy node. Let's say
-
Iteration:
- The list is now
0->1->2->2->3
withpre
at0
andcur
at1
. cur.next
is2
. Sincecur.val
is not equal tocur.next.val
, we movepre
tocur
, andcur
tocur.next
.- Now
pre
is at1
andcur
is at the first2
.
- The list is now
-
Identifying Duplicates:
cur.next
is also2
. Sincecur.val
equalscur.next.val
, we movecur
tocur.next
. Now,cur
is at the second2
.- After the inner loop,
cur.next
is3
, which is not equal tocur.val
. Sincepre.next
(which is the first2
) is not equal tocur
(which is the second2
), we found duplicates.
-
Link Adjustment:
- We link
pre.next
tocur.next
, effectively removing both2
s. The list now becomes0->1->3
.
- We link
-
Move to Next Node:
- Move
cur
tocur.next
, which is3
. cur.next
isnull
now, ending the iteration.
- Move
-
Result:
- The final list is pointed to by
dummy.next
, which is1->3
, with all duplicates (2->2
) removed.
- The final list is pointed to by
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.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!