Problem 203: Remove Linked List Elements

Understanding the Problem

A linked list consists of nodes, and each node has:
value → node.val
pointer → node.next

Your job is to traverse the list and skip all nodes having a specific value.

Example:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Explanation: All nodes containing 6 must be removed.

Key point:
The node to be removed may appear at the beginning, in the middle, or at the end.

Approach (Explained in Simple Language)

To remove nodes from a linked list safely, especially the head node, we follow a simple method.

1. Use a dummy node

We create a new node before the real head.
This avoids special-case handling when the first few nodes must be removed.

Dummy → head → …

2. Use a pointer (current) to traverse the list

At each step, check the next node (current.next).

If current.next.val equals the value to remove:
We skip that node by doing:
current.next = current.next.next

Else:
We simply move forward:
current = current.next

3. Finally, return dummy.next

This represents the updated head.

This approach ensures a clean and simple traversal without edge-case issues.

Java Code

public class RemoveLinkedListElements {

    public ListNode removeElements(ListNode head, int val) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode current = dummy;

        while (current.next != null) {

            if (current.next.val == val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // Example usage can be added here
    }
}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Dry Run

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

Constructed list:
1 → 2 → 6 → 3 → 4 → 5 → 6 → null

We create:
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6

current = dummy

Step 1

current = dummy
current.next = 1
1 != 6, so move current to next:

current = 1

Step 2

current = 1
current.next = 2
2 != 6, move current:

current = 2

Step 3

current = 2
current.next = 6
6 == 6, remove the node:

current.next = current.next.next
List becomes:
1 → 2 → 3 → 4 → 5 → 6

current stays at 2

Step 4

current = 2
current.next = 3
3 != 6, move current:

current = 3

Step 5

current = 3
current.next = 4
4 != 6, move current:

current = 4

Step 6

current = 4
current.next = 5
5 != 6, move current:

current = 5

Step 7

current = 5
current.next = 6
6 == 6 → remove it

current.next = current.next.next
List becomes:
1 → 2 → 3 → 4 → 5

current stays at 5

Step 8

current = 5
current.next = null
Stop loop.

Output head = dummy.next

Final Linked List:
[1, 2, 3, 4, 5]

Why This Approach Works

A linked list cannot be manipulated from the previous node easily.
By using a dummy node and always checking current.next, we avoid:

needing to handle removal of the head node separately
null pointer errors
complex branching logic

This makes the algorithm simple, clean, and linear in time:
O(n), where n is number of nodes.