Compile Ready
Module 2 · Basic Operations

Remove Linked List Elements

EasyProblem 4 of 17 8 min read ~15 min to solve LeetCode
Linked ListDummy NodeDeletionTraversal
Asked atMicrosoftAmazonGoogleAppleAdobe

Problem Statement

Given the head of a linked list and an integer val, remove every node whose value equals val and return the new head of the list.

Input

The head pointer of a singly linked list and an integer val to remove.

Output

The head pointer of the list after all nodes with value val have been removed.

Constraints

  • •0 <= number of nodes <= 10000
  • •1 <= Node.val <= 50
  • •0 <= val <= 50

Examples

Example 1

Input: 
head = **1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null**, val = 6
Output: **1 -> 2 -> 3 -> 4 -> 5 -> null**
Explanation: Both nodes with value **6** are skipped while all other nodes keep their original order.

Example 2

Input: 
head = **7 -> 7 -> 7 -> 7 -> null**, val = 7
Output: **null**
Explanation: Every node matches **val**, including the original head, so the returned list is empty.

Example 3

Input: 
head = **1 -> 2 -> 3 -> null**, val = 4
Output: **1 -> 2 -> 3 -> null**
Explanation: No node has value **4**, so no links are changed.

Learning Objectives

  • Use a dummy head to make deleting the original head identical to deleting an interior node.
  • Maintain **prev** as the last kept node and **curr** as the node being inspected.
  • Explain why **prev** should not advance when **curr** is deleted.
  • Preserve the relative order of all nodes that are not removed.

Intuition

Pattern Recognition

The signal is remove nodes from a singly linked list, especially when the removable node might be the head. Deleting a node requires changing the previous node next pointer, but the original head has no previous node. A dummy head creates a safe previous node before the real list.

The pointer trap is advancing prev after a deletion. If curr is removed, prev.next has been redirected to the next candidate, so prev must stay where it is. This is what correctly removes consecutive matches such as 7 -> 7 -> 7. Advance prev only when curr is kept.

Common mistakes

  • ×Handling head deletions with repeated special cases instead of using a dummy node.
  • ×Advancing **prev** after deleting **curr**, which skips over consecutive nodes that should also be removed.
  • ×Returning the original **head** even though the first one or more nodes may have been deleted.
  • ×Changing **curr.next** without first using **prev.next** to bypass the node from the kept chain.

Algorithm Explanation

Key idea

Place dummy before head so every deletion has a previous node. Keep prev at the last node known to remain in the answer and curr at the node under inspection. If curr.val matches val, bypass it with prev.next = curr.next. Otherwise, move prev forward to curr.

Pointer walkthrough

For dummy -> 1 -> 2 -> 6 -> 6 -> 3 -> null with val = 6, start prev = dummy and curr = 1. Since 1 stays, move both pointers forward so prev = 1 and curr = 2. 2 also stays, so prev = 2 and curr = 6.

Now curr matches. Set prev.next from the first 6 to the second 6, producing dummy -> 1 -> 2 -> 6 -> 3 -> null. Do not move prev; it must remain at 2 because the new prev.next may also need deletion. Inspect the second 6, match again, and set prev.next = 3. Only when curr = 3 is kept does prev move to 3. Return dummy.next to handle head removals correctly.

Algorithm

  1. Create dummy and set dummy.next = head.
  2. Set prev = dummy and curr = head.
  3. While curr is not null, compare curr.val with val.
  4. If they match, bypass curr by setting prev.next = curr.next.
  5. If they do not match, advance prev to curr.
  6. In both cases, advance curr to the next node to inspect.
  7. Return dummy.next as the possibly new head.

Solutions

Solution: Dummy head with prev and curr

Use a dummy node before the list so removing the head uses the same bypass operation as removing any other node. prev tracks the last kept node, while curr scans candidates.

Step-by-step

  1. Create dummy and link it to head.
  2. Set previous to dummy and current to head.
  3. If current.val equals val, set previous.next to current.next and keep previous in place.
  4. Otherwise move previous to current because the node is kept.
  5. Move current to current.next and repeat.
  6. Return dummy.next after the traversal.
Time

O(n)

Space

O(1)

Each node is inspected once, and only a dummy plus two pointers are stored.

Java implementation

Loading…

Dry Run

Sample input

head = 1 -> 2 -> 6 -> 6 -> 3 -> null, val = 6. Consecutive removals show why prev must stay still after deletion.

stepprevcurractionlist from dummy
startdummy1initialise**dummy -> 1 -> 2 -> 6 -> 6 -> 3 -> null**
1dummy1keep 1, move prev**dummy -> 1 -> 2 -> 6 -> 6 -> 3 -> null**
212keep 2, move prev**dummy -> 1 -> 2 -> 6 -> 6 -> 3 -> null**
326delete first 6, prev stays**dummy -> 1 -> 2 -> 6 -> 3 -> null**
426delete second 6, prev stays**dummy -> 1 -> 2 -> 3 -> null**
523keep 3, move prev**dummy -> 1 -> 2 -> 3 -> null**

Returning dummy.next gives 1 -> 2 -> 3 -> null. The same return would also work if the original head had been removed.

Interview Tips

Lead with the dummy node. It shows you understand that head removal should not be a special case. Then be precise about the invariant: prev always points to the last kept node. When curr is deleted, prev does not move because its new next node still has not been inspected.

Likely follow-ups

  • How would you remove the nth node from the end in one pass?
  • How would you remove duplicates from a sorted linked list?
  • How would you partition a list around a value while preserving relative order?
  • How would deletion change in a doubly linked list?

Similar Problems

Partition List
MediumUses dummy heads to build kept chains based on a value test.
Merge Two Sorted Lists
EasyAlso relies on a dummy node to simplify head management.
Remove Nth Node From End of List
MediumAnother deletion problem where a dummy head avoids head-edge cases.
Delete Node in a Linked List
MediumContrasts deletion when you are given the node itself instead of the head.

Key Takeaways

  • A dummy head makes deleting the original head look like deleting any interior node.
  • **prev** means last kept node, not simply the node before the traversal cursor in time.
  • After deleting **curr**, keep **prev** fixed so consecutive matches are not skipped.
  • Return **dummy.next** because the real head may have changed.
Reusable template: Dummy-node deletion: anchor a fake predecessor before head, keep prev on the last retained node, bypass matches, and return dummy.next.