Remove Linked List Elements

easy linked list recursion

Problem

Given the head of a linked list and an integer val, remove all the nodes whose value is val and return the new head.

Inputhead = [1, 2, 6, 3, 4, 5, 6], val = 6

Output[1, 2, 3, 4, 5]

Use a dummy head so the head-deletion case is uniform. Walk with prev; while prev.next.val == val, splice it out; otherwise advance prev.

list (comma-separated)

val

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

function removeElements(head, val) {
  const dummy = { val: 0, next: head };
  let prev = dummy;
  while (prev.next) {
    if (prev.next.val === val) prev.next = prev.next.next;
    else prev = prev.next;
  }
  return dummy.next;
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head), prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == val) prev.next = prev.next.next;
            else prev = prev.next;
        }
        return dummy.next;
    }
}

ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0, head), *prev = &dummy;
    while (prev->next) {
        if (prev->next->val == val) prev->next = prev->next->next;
        else prev = prev->next;
    }
    return dummy.next;
}

Explanation

We need to delete every node whose value equals val, anywhere in the list — even at the very front. A dummy head in front of the real head makes the front case behave exactly like the middle, so we only need one piece of logic.

A prev pointer starts at the dummy and we look at prev.next, the node that might need deleting. If prev.next.val == val, we splice it out with prev.next = prev.next.next and do not move prev, so we can catch several bad nodes in a row.

If the next node is fine, we simply advance prev. Staying put after a deletion is what lets consecutive matching values all get removed correctly.

Example: [1, 2, 6, 3, 4, 5, 6] with val = 6. The 6 in the middle and the 6 at the end are both unlinked, leaving [1, 2, 3, 4, 5].

We return dummy.next as the new head, which is correct even if the original head was deleted. One pass, constant extra space.

Time: O(n) Space: O(1)