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.
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).
while 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:
if cur.val == cur.next.val:
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:
else:
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.
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 use a small example to illustrate the solution approach. Consider the following sorted linked list where some values are duplicated:
1 -> 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
cur
pointing to thehead
(the node with value 1).
Step 2: Traverse the Linked List
- Since
cur
(1) andcur.next
(2) are notNone
, we enter thewhile
loop.
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
cur
points 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.next
to 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
cur
points to the node with value 2, andcur.next
points to the node with value 3, which is distinct. We move to the next node.
Step 7: Repeat Steps 3 to 5
- Now
cur
points to the node with value 3, and we find thatcur.next.val
is 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:
1 -> 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
head
of 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
27
1/**
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}
43
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 // 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};
32
1/**
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};
32
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 of the following shows the order of node visit in a Breadth-first Search?
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
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
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
Want a Structured Path to Master System Design Too? Donāt Miss This!