Skip to main content

203. Remove Linked List Elements

easy

Remove every node from a singly linked list whose value matches a given target. The dummy-head pattern's purest use case — without one, deleting the original head needs special-case code.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Constraints

  • The number of nodes in the list is in the range [0, 10^4].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Examples

Example 1

Input
head = [1,2,6,3,4,5,6], val = 6
Output
[1,2,3,4,5]

Example 2

Input
head = [], val = 1
Output
[]

Example 3

Input
head = [7,7,7,7], val = 7
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

What if the head itself matches val? What if the first several nodes match?

Hint 2

A dummy node placed before head sidesteps the special case. Now every removal is uniform: 'set previous.next = previous.next.next'.

Hint 3

Walk with a single pointer previous starting at the dummy. While previous.next is non-null, either skip the next node (if it matches) or advance previous.

Solution approach

Reveal approach

Dummy-head pointer-rewiring. Allocate a dummy node and link dummy.next = head. Use a single pointer previous starting at dummy. Loop while previous.next is non-null: if previous.next.val == val, set previous.next = previous.next.next (delete without advancing previous, because the new next might also match). Otherwise, advance previous = previous.next. Return dummy.next at the end. The dummy guarantees the head can be removed without special-casing. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • dummy-head
  • pointer-rewiring

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More Linked Lists practice problems

See all Linked Lists problems →