82. Remove Duplicates from Sorted List II

Summary

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the sorted linked list.

Condition:

-100 <= Node.val <= 100

Approach

A sentinel node and runner approach.

We move the runner pointer like this:

Move runner until it reaches a different value.
If runner and current point to the same node, the current value is unique.
Otherwise, the current value is duplicated.

The key point is that the sentinel chain keeps track of the result list. In each loop, we decide whether the current value should be included or skipped.

Function

Initialization:

sentinel = ListNode(101)
current = head
ans = sentinel

Main: While current: runner = current While runner.next and current.val == runner.next.val: runner = runner.next If runner == current: sentinel.next = current sentinel = sentinel.next else: sentinel.next = runner.next current = runner.next

Return ans.next.

Complexity

Time Complexity: O(N) because each node is visited at most once. Space Complexity: O(1).