Remove Duplicates from Sorted List
Drop adjacent duplicates from a sorted singly linked list with one pass.
2 min read
linked-list
Problem#
Given a sorted singly linked list, delete duplicates so each value appears only once.
Examples#
[1,1,2]→[1,2][1,1,2,3,3]→[1,2,3]
Constraints#
0 <= n <= 300.
Approach#
Single pointer. If curr->val == curr->next->val, splice out curr->next; otherwise advance.
Solution#
class Solution {public: ListNode* deleteDuplicates(ListNode* head) { ListNode* curr = head; while (curr && curr->next) { if (curr->val == curr->next->val) { ListNode* del = curr->next; curr->next = del->next; delete del; } else { curr = curr->next; } } return head; }};func deleteDuplicates(head *ListNode) *ListNode { curr := head for curr != nil && curr.Next != nil { if curr.Val == curr.Next.Val { curr.Next = curr.Next.Next } else { curr = curr.Next } } return head}from typing import Optional
class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head while curr and curr.next: if curr.val == curr.next.val: curr.next = curr.next.next else: curr = curr.next return headfunction deleteDuplicates(head) { let curr = head; while (curr && curr.next) { if (curr.val === curr.next.val) { curr.next = curr.next.next; } else { curr = curr.next; } } return head;}class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode curr = head; while (curr != null && curr.next != null) { if (curr.val == curr.next.val) { curr.next = curr.next.next; } else { curr = curr.next; } } return head; }}function deleteDuplicates(head: ListNode | null): ListNode | null { let curr = head; while (curr && curr.next) { if (curr.val === curr.next.val) { curr.next = curr.next.next; } else { curr = curr.next; } } return head;}Editorial#
Sorted invariant means duplicates are adjacent, so a single forward pointer suffices. Don’t advance after a splice — the new neighbor may also be a duplicate.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#