Remove Duplicates from Sorted List II
Medium · Two Pointers · Explanation and code example
Dummy Node and Run Skipping
How it works
Because the list is sorted, every repeated value forms one consecutive run. Keep a pointer to the last accepted node and move the scanning pointer to the end of a run. Keep a run only when it contained one node.
Steps
- Place a dummy before the head.
- Scan to the last node of each equal-value run.
- Advance the accepted pointer for a singleton, or bypass the entire repeated run.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Remove every copy of a repeated value, including the first.
- The dummy handles a repeated run at the head.
- An entirely duplicated list returns an empty list.
Python code example
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(0, head)
prev = dummy
while head:
while head.next and head.val == head.next.val:
head = head.next
if prev.next == head:
prev = prev.next
else:
prev.next = head.next
head = head.next
return dummy.next
C++ code example
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
while (head != nullptr) {
while (head->next && head->val == head->next->val)
head = head->next;
if (prev->next == head)
prev = prev->next;
else
prev->next = head->next;
head = head->next;
}
return dummy.next;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.