83. Remove Duplicates from Sorted List
Problem Description
In this problem, we are provided with the head of a linked list that is already sorted. Our task is to remove any duplicate values from the list. A duplicate is identified when two or more consecutive nodes have the same value. It's important to note that after removing duplicates, the remaining linked list should still be sorted. We must return the modified list with all duplicates deleted, ensuring that each value in the list appears exactly once.
Intuition
The intuition behind the solution comes from the fact that the linked list is already sorted. Since the linked list is sorted, all duplicates of a particular value will be adjacent to each other. We can simply traverse the linked list from the head to the end, and for each node, we check if its value is the same as the value of the next node. If it is, we have found a duplicate, and we need to remove the next node by changing pointers. We update the current node's next pointer to the next node's next pointer, effectively skipping over the duplicate node and removing it from the list. If the values are not identical, we move on to the next node. We repeat this process until we have checked all nodes. The given Python code implements this approach by using a while loop that continues as long as there are more nodes to examine (cur and cur.next are not None).
Learn more about Linked List patterns.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Solution Approach
The implementation of the solution involves a classical algorithm for removing duplicates from a sorted linked list. The algorithm utilizes the fact that a linked list allows for efficient removal of a node by simply rerouting the next pointer of the previous node.
Here's a step-by-step explanation of how the given Python code works:
Step 1: Initialize
A pointer named cur is initialized to point to the head of the linked list.
Step 2: Traverse the Linked List
We use a while loop to go through the linked list. The loop runs as long as cur is not None (indicating that we haven't reached the end of the list) and cur.next is not None (indicating that there is at least one more node to examine for potential duplicates).
1while cur and cur.next:
Step 3: Check for Duplicates
Inside the loop, we compare the current node's value cur.val with the value of the next node cur.next.val.
Step 4: Remove Duplicates
If cur.val equals cur.next.val, we've found a duplicate. Instead of removing the current node, which would be more challenging, we remove the next node. This is accomplished by updating the next pointer of cur to skip the next node and point to the following one:
1if cur.val == cur.next.val:
2 cur.next = cur.next.next
This effectively removes the duplicate node from the list without disturbing the rest of the list's structure.
Step 5: Move to the Next Distinct Element
If no duplicate was found (the else branch), we simply move the pointer cur to the next node to continue the process:
1else:
2 cur = cur.next
Step 6: Return the Updated List
Once the loop is finished (meaning we've reached the end of the list or there are no more items in the linked list), we return the head of the list, which now points to the updated, duplicate-free sorted linked list.
Using this simple yet effective approach, we ensure that the list stays sorted, as we're only removing nodes and not altering the order of the remaining nodes.
Which of the following is a min heap? 
Example Walkthrough
Let's use a small example to illustrate the solution approach. Consider the following sorted linked list where some values are duplicated:
11 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5
We want to remove the duplicate values so that each number is unique in the list.
Step 1: Initialize
- We start with a pointer
curpointing to thehead(the node with value 1).
Step 2: Traverse the Linked List
- Since
cur(1) andcur.next(2) are notNone, we enter thewhileloop.
Step 3: Check for Duplicates
- We compare
cur.val(1) withcur.next.val(2). They are different, so we move to the next node.
Step 4: Is there a Duplicate?
- Now
curpoints to the node with value 2. - We compare
cur.val(2) withcur.next.val(also 2). This time they are the same, signaling a duplicate.
Step 5: Remove Duplicates
- We update
cur.nextto point tocur.next.next. The duplicate node with value 2 is now skipped. - The linked list now looks like this:
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5.
Step 6: Continue Traversing
- The loop continues, and now
curpoints to the node with value 2, andcur.nextpoints to the node with value 3, which is distinct. We move to the next node.
Step 7: Repeat Steps 3 to 5
- Now
curpoints to the node with value 3, and we find thatcur.next.valis also 3. We remove the duplicate as before. - The linked list now looks like:
1 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5. - We continue this process for the remaining nodes with value 4 and finally remove all duplicates.
Step 8: Final Linked List After the while loop finishes, we've removed all duplicates, and our final linked list looks like this:
11 -> 2 -> 3 -> 4 -> 5
Step 9: Return the Updated List
- With no more duplicates left to remove, we exit the while loop and return the
headof the updated list, which is the reference to the first node in our duplicate-free, sorted linked list.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, value=0, next_node=None):
4 self.value = value
5 self.next_node = next_node
6
7class Solution:
8 def deleteDuplicates(self, head: ListNode) -> ListNode:
9 """Remove all duplicates from a sorted linked list such that
10 each element appears only once and return the modified list."""
11
12 # Initialize current to point to the head of the list
13 current = head
14
15 # Traverse the linked list
16 while current and current.next_node:
17 # If the current value is equal to the value in the next node
18 if current.value == current.next_node.value:
19 # Bypass the next node as it's a duplicate
20 current.next_node = current.next_node.next_node
21 else:
22 # Move to the next unique value if no duplicate is found
23 current = current.next_node
24
25 # Return the head of the updated list
26 return head
271/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val; // Value of the node
6 ListNode next; // Reference to the next node in the list
7
8 // Constructor to create a node with no next node
9 ListNode() {}
10
11 // Constructor to create a node with a given value
12 ListNode(int val) { this.val = val; }
13
14 // Constructor to create a node with a given value and next node
15 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
16}
17
18class Solution {
19 /**
20 * Deletes all duplicates such that each element appears only once.
21 *
22 * @param head The head of the input linked list.
23 * @return The head of the linked list with duplicates removed.
24 */
25 public ListNode deleteDuplicates(ListNode head) {
26 // Initialize current to the head of the linked list
27 ListNode current = head;
28
29 // Iterate over the linked list
30 while (current != null && current.next != null) {
31 // If the current node's value is equal to the value of the next node, skip the next node
32 if (current.val == current.next.val) {
33 current.next = current.next.next;
34 } else { // Otherwise, move to the next node
35 current = current.next;
36 }
37 }
38
39 // Return the head of the modified list
40 return head;
41 }
42}
431/**
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 // Function to delete duplicate elements from a sorted linked list
14 ListNode* deleteDuplicates(ListNode* head) {
15 ListNode* current = head; // Create a pointer to iterate through the list
16
17 // Continue iterating as long as the current node and its successor are not null
18 while (current != nullptr && current->next != nullptr) {
19 if (current->val == current->next->val) {
20 // If the current node's value equals the next node's value, skip the next node
21 current->next = current->next->next;
22 } else {
23 // Otherwise, move to the next node
24 current = current->next;
25 }
26 }
27
28 // Return the head of the modified list
29 return head;
30 }
31};
321/**
2 * Definition for singly-linked list node.
3 */
4interface ListNode {
5 val: number;
6 next: ListNode | null;
7}
8
9/**
10 * Deletes all duplicates such that each element appears only once.
11 * @param {ListNode | null} head - The head of the linked list.
12 * @return {ListNode | null} The modified list head with duplicates removed.
13 */
14const deleteDuplicates = (head: ListNode | null): ListNode | null => {
15 let currentNode: ListNode | null = head;
16
17 // Loop through the list while the current node and the next node are not null
18 while (currentNode && currentNode.next) {
19 // Compare the current node value with the next node value
20 if (currentNode.val === currentNode.next.val) {
21 // If they are equal, skip the next node by pointing to node after next.
22 currentNode.next = currentNode.next.next;
23 } else {
24 // If they are not equal, move to the next node
25 currentNode = currentNode.next;
26 }
27 }
28
29 // Return the head of the modified list
30 return head;
31};
32Which data structure is used to implement recursion?
Time and Space Complexity
The time complexity of the provided code is O(n), where n is the number of nodes in the linked list. This is because it involves a single traversal through all the nodes of the list, and for each node, it performs a constant amount of work by checking if the next node has a duplicate value and potentially skipping over duplicates.
The space complexity of the code is O(1), as it only uses a fixed amount of additional memory for the cur pointer. No extra space proportional to the size of the input is needed, whatever the size of the linked list is.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.