Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Input/Output Specifications
- Input: Head of a sorted linked list
- Output: Head of the linked list with duplicates removed
- Constraints:
- The number of nodes in the list is in the range [0, 300]
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order
Examples
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Solutions
Approach 1: Two Pointers (Current and Next)
This approach uses two pointers to traverse the list and skip duplicate nodes.
Algorithm:
- Start with current pointer at head
- While current and current.next exist:
- If current.val equals current.next.val, skip the next node
- Otherwise, move current to the next node
- Return the head
Python:
def deleteDuplicates(head):
"""
Remove duplicates from sorted linked list
Time: O(n)
Space: O(1)
"""
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return head
Java:
class Solution {
/**
* Remove duplicates from sorted linked list
* Time: O(n)
* Space: O(1)
*/
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}
Go:
// deleteDuplicates - Remove duplicates from sorted linked list
// Time: O(n)
// Space: O(1)
func deleteDuplicates(head *ListNode) *ListNode {
current := head
for current != nil && current.Next != nil {
if current.Val == current.Next.Val {
current.Next = current.Next.Next
} else {
current = current.Next
}
}
return head
}
JavaScript:
/**
* Remove duplicates from sorted linked list
* Time: O(n)
* Space: O(1)
*/
function deleteDuplicates(head) {
let current = head;
while (current !== null && current.next !== null) {
if (current.val === current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
C#:
public class Solution {
/// <summary>
/// Remove duplicates from sorted linked list
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode DeleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}
Approach 2: Recursive Solution
This approach uses recursion to remove duplicates by comparing current node with the next node.
Algorithm:
- Base case: if head is null or head.next is null, return head
- If current value equals next value, skip the next node recursively
- Otherwise, recursively process the rest of the list
- Return the head
Python:
def deleteDuplicatesRecursive(head):
"""
Remove duplicates from sorted linked list using recursion
Time: O(n)
Space: O(n) - due to recursion stack
"""
if not head or not head.next:
return head
if head.val == head.next.val:
return deleteDuplicatesRecursive(head.next)
else:
head.next = deleteDuplicatesRecursive(head.next)
return head
Java:
class Solution {
/**
* Remove duplicates from sorted linked list using recursion
* Time: O(n)
* Space: O(n) - due to recursion stack
*/
public ListNode deleteDuplicatesRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val == head.next.val) {
return deleteDuplicatesRecursive(head.next);
} else {
head.next = deleteDuplicatesRecursive(head.next);
return head;
}
}
}
Go:
// deleteDuplicatesRecursive - Remove duplicates from sorted linked list using recursion
// Time: O(n)
// Space: O(n) - due to recursion stack
func deleteDuplicatesRecursive(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
if head.Val == head.Next.Val {
return deleteDuplicatesRecursive(head.Next)
} else {
head.Next = deleteDuplicatesRecursive(head.Next)
return head
}
}
JavaScript:
/**
* Remove duplicates from sorted linked list using recursion
* Time: O(n)
* Space: O(n) - due to recursion stack
*/
function deleteDuplicatesRecursive(head) {
if (head === null || head.next === null) {
return head;
}
if (head.val === head.next.val) {
return deleteDuplicatesRecursive(head.next);
} else {
head.next = deleteDuplicatesRecursive(head.next);
return head;
}
}
C#:
public class Solution {
/// <summary>
/// Remove duplicates from sorted linked list using recursion
/// Time: O(n)
/// Space: O(n) - due to recursion stack
/// </summary>
public ListNode DeleteDuplicatesRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val == head.next.val) {
return DeleteDuplicatesRecursive(head.next);
} else {
head.next = DeleteDuplicatesRecursive(head.next);
return head;
}
}
}
Key Insights
- Sorted property: Since the list is sorted, duplicates are adjacent
- Skip duplicates: When duplicates are found, skip to the next unique node
- In-place modification: Modify the existing list without creating new nodes
- Single pass: Only one traversal needed due to sorted nature
- Edge case handling: Handle empty lists and single nodes properly
Edge Cases
- Empty list (head is null)
- Single node list
- All nodes are duplicates
- No duplicates
- Two consecutive duplicates
- Multiple consecutive duplicates
Test Cases
# Test case 1: Normal case with duplicates
head1 = ListNode(1)
head1.next = ListNode(1)
head1.next.next = ListNode(2)
# Expected: [1,2]
# Test case 2: Multiple duplicates
head2 = ListNode(1)
head2.next = ListNode(1)
head2.next.next = ListNode(2)
head2.next.next.next = ListNode(3)
head2.next.next.next.next = ListNode(3)
# Expected: [1,2,3]
# Test case 3: All duplicates
head3 = ListNode(1)
head3.next = ListNode(1)
head3.next.next = ListNode(1)
# Expected: [1]
# Test case 4: No duplicates
head4 = ListNode(1)
head4.next = ListNode(2)
head4.next.next = ListNode(3)
# Expected: [1,2,3]
# Test case 5: Single node
head5 = ListNode(1)
# Expected: [1]
Follow-up Questions
- How would you handle unsorted lists?
- Can you remove duplicates while keeping only one occurrence?
- How would you handle very large lists?
- What if you need to count the duplicates?
Common Mistakes
- Not handling empty lists
- Incorrectly updating pointers when skipping duplicates
- Not considering single node lists
- Forgetting to move the current pointer when no duplicates
- Memory leaks when not properly managing skipped nodes
- Off-by-one errors in pointer movement