You are given the head of a doubly linked list whose nodes are already sorted in non-decreasing order of their val. Remove every duplicate node so that each value appears exactly once, keeping the first occurrence of each value, and return the head of the updated list.
Each node stores an integer in val and holds two pointers: next (to the node after it) and prev (to the node before it). When you drop a duplicate, the surviving neighbours on both sides must be stitched back together in both directions — the node before the deleted run must point forward past it, and the node after it must point its prev back.
Because the list is sorted, all copies of a value sit next to each other, so you never have to search — the only place a duplicate can hide is immediately after the node you are standing on.
The list is serialized as space-separated values from head to tail, and the answer is printed the same way.
next is enough. The set works but costs O(n) extra space.curr.next to skip the deleted node, and set the new curr.next.prev back to curr (guarding against null when the deleted node was the tail).Input: head = 1 <-> 1 <-> 1 <-> 2 <-> 3 <-> 4 Output: 1 <-> 2 <-> 3 <-> 4 Only the first occurrence of value 1 is kept; the two extra 1s are removed.
Input: head = 1 <-> 2 <-> 2 <-> 3 <-> 3 <-> 4 <-> 4 Output: 1 <-> 2 <-> 3 <-> 4 The repeated 2, 3, and 4 nodes are deleted, leaving one of each.
- 1 <= n <= 10^5 - The list is sorted in non-decreasing order of val. - Node values fit in a 32-bit signed integer.
This looks like a bookkeeping chore, but the fact that the list is sorted turns it into a one-pass, constant-space walk. The arc: first the tempting "remember everything I've seen" approach, then the insight that sorting already lines the duplicates up for you.
Restated plainly: walk the list once; whenever the node in front of you holds the same value as you, unlink that front node and reconnect around it. Keep going until the value in front differs, then step forward.
Worked example — head = 1 <-> 1 <-> 1 <-> 2 <-> 3 <-> 4
stand on 1, next is 1 -> equal, drop the next 1 1 <-> 1 <-> 2 <-> 3 <-> 4 stand on 1, next is 1 -> equal, drop the next 1 1 <-> 2 <-> 3 <-> 4 stand on 1, next is 2 -> different, step forward ... 2,3,4 all distinct -> done answer: 1 <-> 2 <-> 3 <-> 4
Asking these before coding shows you are mapping the input's guarantees to your algorithm instead of assuming them.
“Is the list guaranteed sorted in non-decreasing order?”
This is the whole game — if it is sorted, duplicates are adjacent and one pass suffices; if not, I would need a hash set or a pre-sort.
“Can the list be a single node or entirely one repeated value?”
A one-node list returns unchanged, and all-equal values must collapse to a single node — my loop has to keep unlinking from the same anchor.
“How large can n get?”
Up to 10^5, so an O(n) single pass is comfortable, but I want to avoid O(n) extra memory if the sorted property lets me.
Before I start, I have a couple of clarifying questions.
First and most important — is the list guaranteed sorted in non-decreasing order?
And can the list be a single node or entirely one repeated value, so I collapse it to one?
In a non-decreasing list, if two nodes share a value, every node between them shares it too. So all copies of a value form one contiguous block — you never need to look beyond your immediate next.
1 <-> 1 <-> 1 <-> 2 <-> 3 ^^^^^^^^^^^^^^ one block of 1s, then 2, then 3
Stand on the first copy (the one you keep). As long as curr.next.val == curr.val, splice out curr.next. This keeps the anchor fixed while a whole run of duplicates melts away, and the anchor always has a valid prev.
Move curr forward only when curr.next holds a different value. If you advance eagerly you would step past a duplicate you never removed — the loop condition is what guarantees each value is deduped fully before you leave it.
| Hash set | Adjacent splice | |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
| Needs sorted? |
Both are linear in time, but the sorted guarantee lets the optimal drop the extra memory entirely. The full code for each lives in the Approaches selector below.
Key takeaway
When a list is sorted, duplicates are neighbours — compare each node only with its immediate successor and splice it out in place. Sorted input almost always means you can trade a hash set for O(1) space.
curr = head
while curr and curr.next:
if curr.next.val == curr.val:
unlink curr.next # curr.next = curr.next.next; fix prev
else:
curr = curr.next
return head