No repeats allowed
In a sorted list, delete every value that appears more than once - not just the extra copies, but all of them. About 16 minutes.
Skip the whole run
In a sorted list, equal values sit next to each other. To drop every value that repeats, look at the current node and the one after it. If they match, this value repeats, and the entire run of it must go, including the first copy.
Walk cur to the first node past the run, then point the trailing node, called prev, at it. The first copy is gone because prev no longer points to it.
while cur and cur.val == v:
cur = cur.next # skip every v2 equals the next 2. Skip the whole run of 2s. The trailing node stays on the dummy D.
When the value is unique
If the current node differs from the next one, it is a keeper. Move prev onto it and move cur to the next node.
A dummy node in front of the head is the starting prev. That way, if the very first values are repeated, prev.next can be changed like any other, and there is no special case for the head. Return the dummy's next.
else:
prev = cur
cur = cur.nextThe list is 1, 1, 1, 2. What is the result?
- A2
- B1, 2
- CAn empty list
Show the answer
2. All the 1s repeat, so all three go. Only 2 is left.
Remove all repeated values
Given the head of a sorted singly linked list, delete every node whose value appears more than once in the list, leaving only the values that appear exactly once. Return the head. The result must stay sorted.
head = [1, 2, 3, 3, 4, 4, 5] → [1, 2, 5]
0 ≤ number of nodes ≤ 5,000 · -1,000 ≤ node.val ≤ 1,000 · sorted in non-decreasing order