Linked List Operations: Insert, Delete, Reverse

The single biggest source of bugs in linked-list code is the order in which you reassign pointers. Update next too early and you lose half the list; update it too late and you create a cycle by accident. This post walks through the six operations you will use over and over — insert, delete, reverse, middle, and cycle detection — with diagrams of the pointer state at each step so the right order becomes obvious.

We assume the Node and LinkedList classes from the introduction post:

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

For these examples we will pass head directly rather than wrap it in a class — that is how almost every interview problem is phrased.

Insert at the head

The simplest case. Create a new node whose next is the current head, then make it the new head.

def insert_head(head, value):
    return Node(value, next=head)

Before:                head
│
▼
┌───┐    ┌───┐    ┌───┐
│ 1 │───►│ 2 │───►│ 3 │───► None
└───┘    └───┘    └───┘
After:    head
│
▼
┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 0 │───►│ 1 │───►│ 2 │───►│ 3 │───► None
└───┘    └───┘    └───┘    └───┘

O(1). No traversal needed.

Insert at the tail

If you don’t track a tail pointer, you must walk to the end:

def insert_tail(head, value):
    new = Node(value)
    if head is None:
        return new
    current = head
    while current.next is not None:
        current = current.next
    current.next = new
    return head

O(n). If you maintain a tail reference (as our LinkedList class does), this drops to O(1).

Insert at a position

Walk to the node just before the target position, then splice the new node in:

def insert_at(head, index, value):
    if index == 0:
        return Node(value, next=head)
    current = head
    for _ in range(index - 1):
        if current is None:
            raise IndexError("out of range")
        current = current.next
    if current is None:
        raise IndexError("out of range")
    current.next = Node(value, next=current.next)
    return head

Step 1 — find prev (the node at index-1):
prev
│
▼
┌───┐    ┌───┐
│ 2 │───►│ 3 │───► …
└───┘    └───┘
Step 2 — create new node, point its next at prev.next:
┌───┐    ┌───┐
│ 2 │───►│ 3 │───► …
└───┘    └───┘
▲
│
┌───┐
│ X │
└───┘
Step 3 — point prev.next at new:
┌───┐    ┌───┐    ┌───┐
│ 2 │───►│ X │───►│ 3 │───► …
└───┘    └───┘    └───┘

The order matters — if you reassign prev.next before setting new.next, you lose the rest of the list.

Delete by value

Walk forward while keeping a prev reference. When you find the target, splice it out by setting prev.next to the doomed node’s next:

def delete_value(head, value):
    if head is None:
        return None
    if head.value == value:
        return head.next
    prev = head
    while prev.next is not None and prev.next.value != value:
        prev = prev.next
    if prev.next is not None:
        prev.next = prev.next.next
    return head

The first if handles the special case where the head itself is the target. Forgetting that case is the single most common linked-list bug. Use a dummy head to dodge it entirely:

def delete_value(head, value):
    dummy = Node(0, next=head)
    prev = dummy
    while prev.next is not None:
        if prev.next.value == value:
            prev.next = prev.next.next
            break
        prev = prev.next
    return dummy.next

The dummy node ensures prev is always a real node, so the “delete head” case is no longer special. This trick simplifies dozens of problems.

Delete by position

def delete_at(head, index):
    dummy = Node(0, next=head)
    prev = dummy
    for _ in range(index):
        if prev.next is None:
            raise IndexError("out of range")
        prev = prev.next
    if prev.next is None:
        raise IndexError("out of range")
    prev.next = prev.next.next
    return dummy.next

Same shape: walk to the predecessor, then splice.

Reverse — iteratively

You need three pointers: prev, current, and a temporary next so you don’t lose the rest of the list when you flip a pointer.

def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next       # save what's ahead
        current.next = prev      # flip the pointer
        prev = current           # advance prev
        current = nxt            # advance current
    return prev

Original:    head
│
▼
┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 1 │───►│ 2 │───►│ 3 │───►│ 4 │───► None
└───┘    └───┘    └───┘    └───┘
Mid-reverse (after 2 iterations):
None ◄───┌───┐◄───┌───┐    ┌───┐    ┌───┐
│ 1 │    │ 2 │    │ 3 │───►│ 4 │───► None
└───┘    └───┘    └───┘    └───┘
▲        ▲
prev   current
Final:                                            head
│
▼
┌───┐    ┌───┐    ┌───┐    ┌───┐
None ◄───│ 1 │◄───│ 2 │◄───│ 3 │◄───│ 4 │
└───┘    └───┘    └───┘    └───┘

When the loop ends, current is None and prev points at what used to be the last node — the new head.

Reverse — recursively

The recursive version is shorter and more elegant, though it costs O(n) stack frames:

def reverse_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

The trick: after reverse_rec(head.next) returns, head.next is now the tail of the reversed sub-list. Setting head.next.next = head appends head to that sub-list. Then head.next = None makes head the new last node.

Read the Recursion Fundamentals post if any of that felt fuzzy.

Find the middle — slow and fast pointers

A naive solution counts the nodes, then walks halfway. The classic two-pointer solution does it in one pass:

def middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

fast moves twice as quickly. When it reaches the end, slow is at the midpoint.

Start:
s
│
▼
┌───┐  ┌───┐  ┌───┐  ┌───┐  ┌───┐
│ 1 │─►│ 2 │─►│ 3 │─►│ 4 │─►│ 5 │─► None
└───┘  └───┘  └───┘  └───┘  └───┘
▲
│
f
Step 1:        s            f
Step 2:               s            f (then fast.next is None → stop)
End: slow points at 3, the middle.

For an even-length list, you get the second middle (e.g. node 3 of a 4-node list). If you want the first middle, change the loop to while fast.next and fast.next.next.

Detect a cycle — Floyd’s tortoise and hare

If a linked list contains a cycle, a slow pointer moving one step and a fast pointer moving two steps will eventually meet. If there is no cycle, the fast pointer hits None first.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 1 │───►│ 2 │───►│ 3 │───►│ 4 │
└───┘    └───┘    └───┘    └───┘
▲        │
│        │
└────────┘   (node 4 points back to node 3)
slow moves: 1 → 2 → 3 → 4 → 3 → 4 → …
fast moves: 1 → 3 → 3 → 3 → … (fast laps slow inside the cycle)
They must meet — fast closes the gap by 1 per step.

The reason it works: once both pointers are inside the cycle, the gap between them closes by exactly one node per step. So they must collide within at most one cycle length. We will use the same trick to find the start of the cycle in the practice problems post.

A common bug — the “lost tail”

If you forget to save current.next before flipping it, you cut off the rest of the list:

# wrong — drops nodes 2 onwards
def broken_reverse(head):
    prev = None
    current = head
    while current is not None:
        current.next = prev   # we just lost the original next!
        prev = current
        current = current.next   # current.next is now prev, oops
    return prev

After the first iteration, current.next is None (because prev was None), and the loop exits with only one node. Always cache nxt = current.next first. This pattern shows up in every reversal-style problem.

Practice problems

Solve each before reading the solution.

1. Insert at the tail without a tail pointer

def append(head, value):
    new = Node(value)
    if head is None:
        return new
    current = head
    while current.next is not None:
        current = current.next
    current.next = new
    return head

2. Count nodes

def length(head):
    n = 0
    while head is not None:
        n += 1
        head = head.next
    return n

3. Print all values

def show(head):
    while head is not None:
        print(head.value, end=" -> ")
        head = head.next
    print("None")

4. Get the kth value from the start

def get(head, k):
    for _ in range(k):
        if head is None:
            raise IndexError("out of range")
        head = head.next
    if head is None:
        raise IndexError("out of range")
    return head.value

5. Delete the kth node

def delete_kth(head, k):
    dummy = Node(0, next=head)
    prev = dummy
    for _ in range(k):
        if prev.next is None:
            raise IndexError("out of range")
        prev = prev.next
    if prev.next is None:
        raise IndexError("out of range")
    prev.next = prev.next.next
    return dummy.next

6. Reverse using a stack

A different approach — push every value onto a stack, then walk the list again and overwrite:

def reverse_with_stack(head):
    stack = []
    current = head
    while current is not None:
        stack.append(current.value)
        current = current.next
    current = head
    while current is not None:
        current.value = stack.pop()
        current = current.next
    return head

This uses O(n) extra memory — the in-place version above is preferred.

Recap

You now know:

• Insert/delete are O(1) once you have the predecessor; finding it is O(n)
• The dummy-head trick eliminates the “is it the head?” edge case
• Reversal needs three pointers — save next before flipping
• Slow/fast pointers find the middle in one pass
• The same slow/fast pattern detects cycles (Floyd’s tortoise and hare)
• Updating pointers in the wrong order is the #1 source of bugs

Next steps

Time to put it all together. The next post is eight classic linked-list interview problems — reverse, cycle, merge, remove Nth from end, palindrome, intersection, and more — with worked Python solutions for each.

→ Next: Linked Lists: 8 Practice Problems with Solutions

Questions or feedback? Email codeloomdevv@gmail.com.