80. Remove Duplicates from Sorted List

The list is already sorted, so duplicates are adjacent. Walk one pointer; whenever the next node has the same value, splice it out by pointing past it; otherwise advance.

Duplicates are neighbours

Because the list is sorted ascending, all equal values sit next to each other. A single pass suffices: keep a cur pointer and compare cur.val with cur.next.val.

cur = head
while cur and cur.next:
    if cur.next.val == cur.val:
        cur.next = cur.next.next     # unlink the duplicate
    else:
        cur = cur.next               # values differ -> advance
return head

Note we only advance cur when the values differ — after removing a duplicate we stay put so a run of three or more equal values collapses correctly.

Worked example

head = 1 -> 1 -> 2 -> 3 -> 3.

• cur=1, next 1 equal → unlink → 1 -> 2 -> 3 -> 3.
• cur=1, next 2 differ → advance.
• cur=2, next 3 differ → advance.
• cur=3, next 3 equal → unlink → 1 -> 2 -> 3.
• cur=3, no next → stop.

Result: 1 -> 2 -> 3.

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == cur.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}