LeetCode 237 · Linked list

Delete Node in a Linked List, explained with a picture

Removing a coach you’re standing in.

Linked list
▶ Watch it step by step

The problem

Delete a given node from a linked list when you are given only that node (not the head). It is never the last node.

Input:  4 → 5 → 1 → 9, delete 5
Output: 4 → 1 → 9

Picture it

Picture standing inside a coach you’re told to remove, with no way to reach the coach in front. Trick: copy the next coach’s number into yours, then uncouple the next coach instead. The train looks exactly as if your coach was removed.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

node.val = node.next.val; node.next = node.next.next. O(1).

Python solution

def delete_node(node):          # no access to head
    node.val = node.next.val
    node.next = node.next.next

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.