DSA sheet · Linked List · Merge / Sort pattern

Remove Duplicates from Sorted List

The second problem of the merge / sort pattern. The list is sorted, and the teacher asks us to underline that word, because it is the key to the fast answer: in a sorted list, equal values always sit next to each other. She first shows why a set is the wrong tool, then a brute force that collects the unique values in an array and writes them back into the nodes, and finally the in-place answer that just skips over each duplicate node with one pointer.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists from scratch (and deleting a node)
• Part A · Brute force: collect unique values, overwrite the nodes
• Part B · Optimal: skip duplicates in place
• Part C · Revision page

Part 0 · Before starting

What is a node?

A linked list is a chain of nodes. Each node holds a value (val) and a link to the next node (next). The last node's next is None: the chain ends there.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end

  [1] → [1] → [2] → [3] → [3] → None
   ↑
  head

The head is the first node; through it we can reach the whole list. An empty list has head = None.

Walking a list

Keep a pointer curr, start it at the head, and step with curr = curr.next until it is None. Because we must not lose the head (we have to return it), we walk with a copy of it, an "alias" as the teacher calls it.

curr = head            # alias: head itself stays put
while curr is not None:
    print(curr.val)
    curr = curr.next

No index access

Arrays jump to a[i] in one step. In a linked list the nodes are scattered in memory and each one only knows the next, so reaching position i means walking i steps from the head: O(n). That's why the brute force below needs a separate Python list if it wants to say "the last value I kept".

Deleting a node = skipping it

To remove the node after curr, we don't "erase" anything. We just make curr point past it:

  before:  [1] → [1] → [2] → ...
            ↑     ↑
          curr   to delete

  curr.next = curr.next.next

  after:   [1] ──────→ [2] → ...       the second [1] is no longer reachable
            ↑
          curr

Nothing points to the skipped node any more, so it's gone from the list (Python's garbage collector frees it). Note the rule save before you overwrite: here it's automatic, because we read curr.next.next (the node we want to keep) in the same line where we overwrite curr.next.

What does "sorted" give us?

In a sorted list, all copies of a value form one block of neighbours: 1, 1, 2, 3, 3. So to know whether a node is a duplicate, you only ever need to compare it with the node right before it (or right after it). You never need to remember every value you've seen.

Part A · Brute force: collect unique values, overwrite the nodes

LeetCode 83

1The question in simple words

You get the head of a sorted linked list. Remove extra copies so that each value appears only once. The result must still be sorted. Return the head.

  input:  [1] → [1] → [2] → [3] → [3] → None
  output: [1] → [2] → [3] → None

Note: we keep one copy of each value (in Problem 22 you'll remove every value that has duplicates, which is different).

2What the constraints tell us

• Number of nodes: 0 to 300. 0 is allowed → base case: if the head is None, there's nothing to remove, return None.
• 300 is small. Linked list solutions are almost always linear, so TLE is not a worry here. The real goal is to optimise, especially the space.
• Values are between −100 and 100 and the list is sorted in ascending order. The "sorted" part is what we'll use.

3Intuition: first try with a set (and why it's wrong)

If this were a plain array, the first idea is: put every value in a set. A set keeps only unique values. Then make a new list from the set.

The problem: a set doesn't keep order. From 1, 1, 2, 3, 3 the set might hand the values back as 2, 1, 3. A new list built from that would be 2 → 1 → 3, not sorted. To fix it you'd have to sort again, and the teacher's point is: why sort, when the question already gave us a sorted list? So no set.

Better idea: walk the list and keep a growing Python list of the values we decided to keep. Because the input is sorted, a value is a duplicate exactly when it equals the last value we kept.

4Building the logic from the example

List: 1 → 1 → 2 → 3 → 3. kept = [].

1. curr on the first 1. kept is empty, so there's nothing to compare with → add 1. kept = [1].
2. curr on the second 1. Last kept value (kept[-1], the teacher's "size − 1" index) is 1, equal → duplicate → don't add. Just move on.
3. curr on 2. Last kept is 1, different → add. kept = [1, 2].
4. curr on 3. Different from 2 → add. kept = [1, 2, 3].
5. curr on the second 3. Same as last kept → skip.
6. curr becomes None → stop. Whether we added or not, curr moved one step each time, so the loop is while curr is not None.

Now turn kept back into a linked list

Two choices the teacher mentions:

• Build a new linked list from kept and return its head (more new nodes).
• Better: overwrite the values of the original nodes. The original list has at least as many nodes as kept (here 5 vs 3), so there's always room. Write kept[0], kept[1], kept[2] into the first 3 nodes, then cut the list after the third node by setting its next to None.

  kept = [1, 2, 3]
  index:   0     1     2
          [1] → [2] → [3] ✂ [3] → [3] → None
                       ↑
              last index: set .next = None

5Approach steps

1. If head is None → return None.
2. Walk the list; add curr.val to kept when kept is empty or its last value differs.
3. Walk again from head for i = 0 … len(kept) − 1: write kept[i] into the node. If i is the last index, set next = None; otherwise move forward.
4. Return head.

6Code (Python)

class Solution:
    def deleteDuplicates(self, head):
        if head is None:                       # 0 nodes
            return None

        kept = []
        curr = head
        while curr is not None:
            if not kept or kept[-1] != curr.val:
                kept.append(curr.val)          # new value, keep it
            curr = curr.next                   # move on either way

        curr = head
        for i in range(len(kept)):
            curr.val = kept[i]                 # overwrite in place
            if i == len(kept) - 1:
                curr.next = None               # cut off the leftovers
            else:
                curr = curr.next
        return head

7Code line by line

8Dry run: 1 → 1 → 2 → 3 → 3

9Complexity & remember

• Time O(n), more exactly up to 2n: one full walk to fill kept, then up to n more steps to overwrite. The teacher points out the best case: if all values are the same, kept has one value and the second loop runs once. The worst case is no duplicates: kept gets all n values and the second loop also runs n times → 2n.
• Space O(n) for the kept list.

Part B · Optimal: skip duplicates in place

1The question in simple words

Same question. Can we do it with no extra space? The teacher says that's the main concern in linked list questions; changing the list itself with O(1) extra memory is called working in place.

2What the constraints tell us

• Sorted → duplicates are neighbours → compare curr with curr.next. No memory of older values needed.
• 0 nodes → the loop condition curr is not None already handles it (we return head = None).

3Intuition: a train with repeated carriages

Stand on a carriage and look at the one right behind it. If it carries the same number, unhook it and couple your carriage to the one after. Stay where you are and look again, because the new neighbour may also be a copy. Only when your neighbour is different do you step forward.

4Building the logic from the example

List 1 → 1 → 2 → 3 → 3, with curr on the head.

What must be true to compare?

We compare curr.val with curr.next.val, so we need both nodes to exist: while curr is not None and curr.next is not None.

Same value → unhook the next node

1 and 1 match, so the second 1 is a duplicate. curr.next = curr.next.next: the first 1 now points straight to 2.

Different value → move forward

1 vs 2: different, so nothing after curr is a copy of 1. Move: curr = curr.next. Then 2 vs 3: different, move. Then 3 vs 3: same → curr.next = curr.next.next, which is None. Now curr.next is None, so the loop stops.

What to return?

The head never changes here (the first node is always kept: it's the first copy of its value), so we return head.

5Approach steps

1. curr = head.
2. While curr and curr.next exist:
   • same values → curr.next = curr.next.next (don't move);
   • different → curr = curr.next.
3. Return head.

6Code (Python)

class Solution:
    def deleteDuplicates(self, head):
        curr = head
        while curr is not None and curr.next is not None:
            if curr.val == curr.next.val:
                curr.next = curr.next.next     # unhook the duplicate
            else:
                curr = curr.next               # neighbour differs, move on
        return head

7Code line by line

8Dry run: 1a → 1b → 2 → 3a → 3b

  start:      [1a] → [1b] → [2] → [3a] → [3b] → None
               curr

  after 1:    [1a] ────────→ [2] → [3a] → [3b] → None
               curr          (1b skipped)

  after 3:    [1a] → [2] → [3a] → [3b] → None
                            curr

  after 4:    [1a] → [2] → [3a] → None
                            curr    curr.next is None → stop

A block of three, 1 → 1 → 1 → 2: step 1 skips the second 1 (curr stays), step 2 skips the third 1 (curr stays), step 3 sees 1 vs 2 and moves. Result 1 → 2 ✓.

9Complexity & remember

• Time O(n): every loop round either removes one node or moves curr one step; either way it happens at most n times. One pass.
• Space O(1): just one pointer. No array, no new nodes. That's why it also ran faster on LeetCode.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.deleteDuplicates(build([1, 1, 2, 3, 3]))))  # [1, 2, 3]
print(to_list(s.deleteDuplicates(build([1, 1, 1, 2]))))     # [1, 2]
print(to_list(s.deleteDuplicates(build([]))))               # []
print(to_list(s.deleteDuplicates(build([7, 7, 7]))))        # [7]

Based on this video: Remove Duplicates from Sorted List