Remove Duplicates from Sorted List

How it works

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.

Steps

1. Start with a pointer cur at the head.
2. While both cur and cur.next exist:
   • If they have the same value, skip the next node by updating cur.next.
   • Otherwise, advance cur to the next node.
3. Return the head.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

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.

from typing import Optional

# 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 head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        while (cur && cur->next) {
            if (cur->next->val == cur->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};