Remove Linked List Elements (LeetCode 203)
Branchless Head Mutation via a Synthetic Predecessor
Given a singly linked list, execute structural modifications (such as deleting target nodes, merging multiple lists, partitioning by value, or reversing sub-segments) where the head node itself may be modified or removed, in time with zero branching edge cases.
The Technique Invariant: Instead of cluttering list algorithms with special-case logic for empty lists (head == null) or head deletions (if curr == head), prepend a synthetic Sentinel (Dummy) Node: dummy = ListNode(0, head).
- The sentinel node guarantees that every valid list node—including the original head—possesses a non-null predecessor pointer (
prev.next = curr.next). - Edge cases of deleting the first element, inserting before the head, or operating on single-element lists become identical to internal node operations.
- Return
dummy.nextas the sanitized, unambiguous head of the modified list.
Worked Examples
head = [1,2,6,3,4,5,6], val = 6[1,2,3,4,5]head = [], val = 1[]head = [7,7,7,7], val = 7[]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range [0, 10^4]
1 <= Node.val <= 50
0 <= val <= 50
Why It Works & Core Invariant
\forall nodes v ∈ List, ; predecessor(v) e null — the dummy node guarantees uniform node deletion and insertion semantics.
Real-World Scenario & Production Applications
Java's LinkedList/LinkedHashMap and Redis's list implementations keep permanent sentinel head/tail nodes so insertion, removal, and LRU eviction never special-case the boundary elements; the Linux kernel's intrusive struct list_head anchors circular doubly-linked lists the same way to avoid null-pointer checks inside interrupt handlers.
| 1 | Prepend a dummy node before head: dummy = ListNode(0, head) |
| 2 | Initialize prev = dummy, curr = head |
| 3 | If curr.val == val: prev.next = curr.next; else advance prev = curr |
| 4 | Advance curr = curr.next every iteration and return dummy.next |
Target: Remove Linked List Elements (LeetCode 203). Creates a synthetic predecessor for the real head, so the very first node no longer needs special-case handling when it is removed.
Initialize dummy_head.next = head (or dummy_head.next = dummy_tail for doubly-linked). All operations return dummy_head.next.
dummy = ListNode(0); dummy.next = head; prev = dummy; while curr: ...; return dummy.next
Conceptual Narrative
The Flash of Genius: Deleting or replacing a linked list's head node forces every mutation to branch on
if curr == head, since the head has no predecessor to redirect. Prepending a synthetic dummy node before the real head (dummy = ListNode(0, head)) gives every node -- including the original head -- a valid predecessor. Every removal collapses to the single uniform line prev.next = curr.next, and the sanitized result is always dummy.next.
The Mental Model Analogy: The Physical Bookends on a Crowded Shelf
Imagine organizing books on an open-ended shelf. If there are no bookends, whenever you want to insert a new book at the very left edge, you have to be extremely careful that the book does not tumble off the shelf onto the floor! You need a special rule for the first book, a special rule for the last book, and a general rule for books in the middle. But if you screw two heavy steel bookends permanently into the wood at position 0 and position 100—bookends that are never removed—now EVERY book, even the very first and very last, is always nestled comfortably between two existing objects! You no longer need special edge cases for 'inserting at head' or 'deleting at tail'. One single, universal rule handles 100% of cases without a single dropped book.
Pitfall: Deleting the head node normally needs a special case because it has no predecessor to redirect -- what gives it one?
Pitfall: Once prev starts at the dummy node, prev.next = curr.next works identically no matter which node is removed.
Pitfall: The final answer is never head directly -- it's always dummy.next, since the true head may have been removed.
4-Phase Thought Process Model
Senior SWE thought process architecture for Sentinel (Dummy Head) Node Injection.
Pattern Recognition Signals
The 10-second spot
The operation modifies a linked list, and the head node might be removed, swapped, or prepended. Instantiate a dummy sentinel node.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Initialize prev = dummy and curr = head. Now every node, including index 0, has a valid prev pointer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Invariant:
dummy_head.nextis the most recent;dummy_tail.previs the least recent.Zero branches: Adding and removing nodes never checks for
None.
The 60-Second Interview Pitch
Say this out loud before you type a single line
Verify on empty lists
head = Noneand singleton lists[1]. Both execute cleanly through the general loop without crashing.
Deleting or replacing a linked list's head node forces every mutation to branch on if curr == head, since the head has no predecessor to redirect. Prepending a synthetic dummy node before the real head (dummy = ListNode(0, head)) gives every node -- including the original head -- a valid predecessor. Every removal collapses to the single uniform line prev.next = curr.next, and the sanitized result is always dummy.next.
Complexity & Mathematical Proof
O(n)
Allocating a sentinel dummy node takes O(1) time. By eliminating conditional branch checks (if head is None, if curr.next is None) inside the traversal loop, the instruction count per iteration decreases. Total traversal time is strictly O(N) with fewer total CPU instructions.
O(1)
Exactly one dummy node (or two in doubly-linked structures) is allocated on the heap or stack. Auxiliary space complexity is strictly O(1).
Allocating a sentinel dummy node takes O(1) time. By eliminating conditional branch checks (if head is None, if curr.next is None) inside the traversal loop, the instruction count per iteration decreases. Total traversal time is strictly O(N) with fewer total CPU instructions.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Instantiates dummy = ListNode(0, head) without being prompted by the interviewer. • Returns dummy.next rather than attempting to track a mutable head reference. • Designs LRU Cache with two sentinel nodes (head and tail) to achieve branchless node splicing. • Explains CPU branch predictor benefits of removing boundary condition checks.
The number of nodes in the list is in the range [0, 10^4]. 1 <= Node.val <= 50. 0 <= val <= 50
In the Linux kernel linked list implementation (<linux/list.h>), all circular doubly-linked lists use a sentinel struct list_head anchor to avoid null pointer dereferencing in kernel interrupt handlers.
Core Algorithmic State Invariants
The right pointer advances forward, absorbing the incoming element into the running aggregation state (frequency map, sum, or set).
When window constraints are violated (or while valid when seeking minimal length), the left pointer increments to evict elements and restore the required invariant.
Because each element enters and exits the window at most once, total operations across both pointers are bounded by 2N, guaranteeing strictly linear O(N) execution.
Remove Linked List Elements (LeetCode 203)
Branchless Head Mutation via a Synthetic Predecessor
Given a singly linked list, execute structural modifications (such as deleting target nodes, merging multiple lists, partitioning by value, or reversing sub-segments) where the head node itself may be modified or removed, in time with zero branching edge cases.
The Technique Invariant: Instead of cluttering list algorithms with special-case logic for empty lists (head == null) or head deletions (if curr == head), prepend a synthetic Sentinel (Dummy) Node: dummy = ListNode(0, head).
- The sentinel node guarantees that every valid list node—including the original head—possesses a non-null predecessor pointer (
prev.next = curr.next). - Edge cases of deleting the first element, inserting before the head, or operating on single-element lists become identical to internal node operations.
- Return
dummy.nextas the sanitized, unambiguous head of the modified list.
Worked Examples
head = [1,2,6,3,4,5,6], val = 6[1,2,3,4,5]head = [], val = 1[]head = [7,7,7,7], val = 7[]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range [0, 10^4]
1 <= Node.val <= 50
0 <= val <= 50
Why It Works & Core Invariant
\forall nodes v ∈ List, ; predecessor(v) e null — the dummy node guarantees uniform node deletion and insertion semantics.
Real-World Scenario & Production Applications
Java's LinkedList/LinkedHashMap and Redis's list implementations keep permanent sentinel head/tail nodes so insertion, removal, and LRU eviction never special-case the boundary elements; the Linux kernel's intrusive struct list_head anchors circular doubly-linked lists the same way to avoid null-pointer checks inside interrupt handlers.
| 1 | Prepend a dummy node before head: dummy = ListNode(0, head) |
| 2 | Initialize prev = dummy, curr = head |
| 3 | If curr.val == val: prev.next = curr.next; else advance prev = curr |
| 4 | Advance curr = curr.next every iteration and return dummy.next |
Target: Remove Linked List Elements (LeetCode 203). Creates a synthetic predecessor for the real head, so the very first node no longer needs special-case handling when it is removed.
Initialize dummy_head.next = head (or dummy_head.next = dummy_tail for doubly-linked). All operations return dummy_head.next.
dummy = ListNode(0); dummy.next = head; prev = dummy; while curr: ...; return dummy.next
Conceptual Narrative
The Flash of Genius: Deleting or replacing a linked list's head node forces every mutation to branch on
if curr == head, since the head has no predecessor to redirect. Prepending a synthetic dummy node before the real head (dummy = ListNode(0, head)) gives every node -- including the original head -- a valid predecessor. Every removal collapses to the single uniform line prev.next = curr.next, and the sanitized result is always dummy.next.
The Mental Model Analogy: The Physical Bookends on a Crowded Shelf
Imagine organizing books on an open-ended shelf. If there are no bookends, whenever you want to insert a new book at the very left edge, you have to be extremely careful that the book does not tumble off the shelf onto the floor! You need a special rule for the first book, a special rule for the last book, and a general rule for books in the middle. But if you screw two heavy steel bookends permanently into the wood at position 0 and position 100—bookends that are never removed—now EVERY book, even the very first and very last, is always nestled comfortably between two existing objects! You no longer need special edge cases for 'inserting at head' or 'deleting at tail'. One single, universal rule handles 100% of cases without a single dropped book.
Pitfall: Deleting the head node normally needs a special case because it has no predecessor to redirect -- what gives it one?
Pitfall: Once prev starts at the dummy node, prev.next = curr.next works identically no matter which node is removed.
Pitfall: The final answer is never head directly -- it's always dummy.next, since the true head may have been removed.
4-Phase Thought Process Model
Senior SWE thought process architecture for Sentinel (Dummy Head) Node Injection.
Pattern Recognition Signals
The 10-second spot
The operation modifies a linked list, and the head node might be removed, swapped, or prepended. Instantiate a dummy sentinel node.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Initialize prev = dummy and curr = head. Now every node, including index 0, has a valid prev pointer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Invariant:
dummy_head.nextis the most recent;dummy_tail.previs the least recent.Zero branches: Adding and removing nodes never checks for
None.
The 60-Second Interview Pitch
Say this out loud before you type a single line
Verify on empty lists
head = Noneand singleton lists[1]. Both execute cleanly through the general loop without crashing.
Deleting or replacing a linked list's head node forces every mutation to branch on if curr == head, since the head has no predecessor to redirect. Prepending a synthetic dummy node before the real head (dummy = ListNode(0, head)) gives every node -- including the original head -- a valid predecessor. Every removal collapses to the single uniform line prev.next = curr.next, and the sanitized result is always dummy.next.
Complexity & Mathematical Proof
O(n)
Allocating a sentinel dummy node takes O(1) time. By eliminating conditional branch checks (if head is None, if curr.next is None) inside the traversal loop, the instruction count per iteration decreases. Total traversal time is strictly O(N) with fewer total CPU instructions.
O(1)
Exactly one dummy node (or two in doubly-linked structures) is allocated on the heap or stack. Auxiliary space complexity is strictly O(1).
Allocating a sentinel dummy node takes O(1) time. By eliminating conditional branch checks (if head is None, if curr.next is None) inside the traversal loop, the instruction count per iteration decreases. Total traversal time is strictly O(N) with fewer total CPU instructions.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Instantiates dummy = ListNode(0, head) without being prompted by the interviewer. • Returns dummy.next rather than attempting to track a mutable head reference. • Designs LRU Cache with two sentinel nodes (head and tail) to achieve branchless node splicing. • Explains CPU branch predictor benefits of removing boundary condition checks.
The number of nodes in the list is in the range [0, 10^4]. 1 <= Node.val <= 50. 0 <= val <= 50
In the Linux kernel linked list implementation (<linux/list.h>), all circular doubly-linked lists use a sentinel struct list_head anchor to avoid null pointer dereferencing in kernel interrupt handlers.
Core Algorithmic State Invariants
The right pointer advances forward, absorbing the incoming element into the running aggregation state (frequency map, sum, or set).
When window constraints are violated (or while valid when seeking minimal length), the left pointer increments to evict elements and restore the required invariant.
Because each element enters and exits the window at most once, total operations across both pointers are bounded by 2N, guaranteeing strictly linear O(N) execution.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| dummy = ListNode(0, head) | dummy = ListNode(0, head) | Creates a synthetic predecessor for the real head, so the very first node no longer needs special-case handling when it is removed. |
| prev, curr = dummy, head | prev, curr = dummy, head | Anchors prev at the sentinel so the loop invariant prev.next == curr holds even on the first iteration. |
| if should_remove(curr, target): prev.next = curr.next | if curr.val == val:
prev.next = curr.next | Removes the current node with the exact same line whether it is the original head, an interior node, or the tail -- zero branching on position. |
| return dummy.next | return dummy.next | Returns the sanitized head. If the original head itself was removed, dummy.next already points at its replacement automatically. |