83. Remove Duplicates From Sorted List - Explanation
Description
The singly linked list starting at head is sorted in nondecreasing order. Remove duplicate nodes so that each distinct value remains exactly once, and return the head of the resulting list. Preserve the sorted order. In the examples and test inputs, an array lists node values from head to tail; [] represents an empty list.
Example 1:
Input: head = [0,0,1,2,2,2]
Output: [0,1,2]Explanation: Keep one node with value 0, the node with value 1, and one node with value 2. The resulting chain is 0 -> 1 -> 2.
Example 2:
Input: head = [5,5,5]
Output: [5]Explanation: All three nodes have the same value. Keep one node with value 5.
Example 3:
Input: head = []
Output: []Explanation: The input list is empty, so there are no nodes to remove and the result is empty.
Constraints:
- The list contains between
0and300nodes. -100 <= Node.val <= 100- Node values are sorted in nondecreasing order.
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Linked List Fundamentals - Understanding node structure, traversal, and pointer manipulation
- Recursion - Processing linked lists recursively from the tail back to the head
- Sorted Data Structures - Leveraging the fact that duplicates are adjacent in sorted lists
1. Recursion
Intuition
We solve the problem from the end of the list backward. First, we recursively remove duplicates from the rest of the list, then check if the current node duplicates its (now cleaned) next node. If so, we skip the current node by returning its next. This naturally handles chains of duplicates.
Algorithm
- Base case: if the list is empty or has one node, return it.
- Recursively clean the rest of the list starting from
head.next. - Update
head.nextto point to the cleaned sublist. - If the current node's value equals the next node's value, return
head.next(skip current). - Otherwise, return
head(keep current).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
head.next = self.deleteDuplicates(head.next)
return head if head.val != head.next.val else head.nextTime & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
2. Iteration - I
Intuition
Since the list is sorted, duplicates are consecutive. At each node, we skip over all following nodes with the same value by adjusting the next pointer. This removes entire chains of duplicates in one pass through the list.
Algorithm
- Start with a pointer
curat the head. - While
curis notnull, check if the next node has the same value. - If so, skip the next node by setting
cur.next = cur.next.next. - Continue skipping until the next node has a different value.
- Move
curto the next node and repeat. - Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur:
while cur.next and cur.next.val == cur.val:
cur.next = cur.next.next
cur = cur.next
return headTime & Space Complexity
- Time complexity:
- Space complexity: extra space.
3. Iteration - II
Intuition
A slightly different structure: instead of a nested loop, we use a single loop with a conditional. If the current and next values match, we skip the next node. If they differ, we advance the pointer. This achieves the same result with cleaner control flow.
Algorithm
- Start with a pointer
curat the head. - While both
curandcur.nextexist:- If they have the same value, skip the next node by updating
cur.next. - Otherwise, advance
curto the next node.
- If they have the same value, skip the next node by updating
- Return the head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return headTime & Space Complexity
- Time complexity:
- Space complexity: extra space.
Common Pitfalls
Advancing the Pointer Incorrectly
When removing a duplicate, you should only update cur.next to skip the duplicate node, but not advance cur itself. If you move cur forward after removing a node, you might skip checking whether the new next node is also a duplicate. Only advance cur when the next node has a different value.
Not Handling Null Pointers
When accessing cur.next.val, you must first verify that cur.next is not null. Forgetting this check leads to null pointer exceptions on the last node or empty lists. Always structure your loop condition as while cur and cur.next or check cur.next != null before accessing its value.
Sign in to join the discussion