Linked List Problems: Every Pattern You Need to Know

Linked list problems are a staple of coding interviews, and they tend to trip people up more than they should. The data structure itself is simple — nodes pointing to other nodes. But the pointer manipulation can get confusing, especially under interview pressure. Off-by-one errors, losing references, accidentally creating cycles — these are easy mistakes to make.

The good news: linked list problems use a small set of patterns. Learn these patterns, and you can solve any linked list problem they throw at you.

The Node Definition

Throughout this article, we'll use this standard definition:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Nothing fancy. A value and a pointer to the next node.

Pattern 1: Fast and Slow Pointers

The fast pointer moves two steps at a time, the slow pointer moves one step. This simple idea solves a surprising number of problems.

Problem: Detect a Cycle

Does a linked list have a cycle?

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

If there's a cycle, the fast pointer eventually laps the slow pointer and they meet. If there's no cycle, the fast pointer hits the end. This is Floyd's cycle detection algorithm.

Why does it work? Once both pointers are in the cycle, the distance between them decreases by 1 on each step (fast gains 1 step, so the gap shrinks by 1). They must eventually meet.

O(n) time, O(1) space.

Problem: Find the Cycle Start

If there's a cycle, where does it begin?

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # phase 2: find the start
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

The math: when slow and fast meet, slow has traveled distance d (from head to cycle start) plus k (distance into the cycle). Fast has traveled 2(d + k). The difference d + k is a multiple of the cycle length. Resetting slow to head and moving both one step at a time, they meet at the cycle start after d steps.

You don't need to memorize the proof for interviews, but understanding why the reset works helps you reconstruct the algorithm if you forget it.

Problem: Find the Middle Node

Return the middle node of a linked list. If two middle nodes exist, return the second one.

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast reaches the end, slow is at the middle. That's it. No counting, no two-pass solution.

If you need the first middle (for even-length lists), change the condition to while fast.next and fast.next.next.

Problem: Linked List Cycle Length

Once you find the meeting point, keep one pointer fixed and move the other until they meet again, counting steps.

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            count = 1
            current = slow.next
            while current != slow:
                count += 1
                current = current.next
            return count
    return 0

Problem: Remove Nth Node From End

Remove the nth node from the end in one pass.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy

# advance fast by n+1 steps
    for _ in range(n + 1):
        fast = fast.next

# move both until fast hits end
    while fast:
        slow = slow.next
        fast = fast.next

slow.next = slow.next.next
    return dummy.next

The gap between fast and slow is n + 1. When fast reaches the end, slow is right before the node to remove. The dummy head handles the edge case where we need to remove the head node.

Problem: Palindrome Linked List

Check if a linked list is a palindrome in O(1) space.

def is_palindrome(head):
    # find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

# reverse second half
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

# compare halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

return True

Three patterns in one: find middle (fast/slow), reverse a linked list, and compare two lists.

Pattern 2: Reversal

Reversing a linked list (or part of it) is the second most important pattern. It shows up both as its own problem and as a building block for harder problems.

Iterative Reversal

def reverse_list(head):
    prev = None
    current = head
    while current:
        nxt = current.next    # save next
        current.next = prev   # reverse link
        prev = current        # advance prev
        current = nxt         # advance current
    return prev

Three pointers: prev, current, and nxt. At each step, reverse the link, then advance all three. When current is None, prev is the new head.

Draw this on paper if it's not clicking. Seriously. Linked list reversal is one of those things that's much clearer with a diagram.

Recursive Reversal

def reverse_list_recursive(head):
    if not head or not head.next:
        return head

new_head = reverse_list_recursive(head.next)
    head.next.next = head    # reverse the link
    head.next = None         # prevent cycle
    return new_head

The recursion reaches the last node, which becomes the new head. On the way back up the call stack, each node reverses the link to the node before it.

Problem: Reverse Linked List II (Reverse Between Positions)

Reverse nodes from position left to position right.

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy

# move prev to just before the reversal starts
    for _ in range(left - 1):
        prev = prev.next

# reverse the sublist
    current = prev.next
    for _ in range(right - left):
        nxt = current.next
        current.next = nxt.next
        nxt.next = prev.next
        prev.next = nxt

return dummy.next

The trick: instead of reversing all links, repeatedly move the next node to the front of the reversed section. prev stays fixed, current stays fixed, and we keep pulling nodes from after current to right after prev.

Problem: Reverse Nodes in K-Group

Reverse every k nodes in the list. If the remaining nodes are fewer than k, leave them as-is.

def reverse_k_group(head, k):
    # check if there are k nodes remaining
    count = 0
    node = head
    while node and count < k:
        node = node.next
        count += 1

if count < k:
        return head

# reverse k nodes
    prev = None
    current = head
    for _ in range(k):
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt

# head is now the tail of the reversed group
    # recursively reverse the rest
    head.next = reverse_k_group(current, k)

return prev

Recursive approach: reverse the first k nodes, then recurse on the rest. The original head becomes the tail of the reversed group and connects to whatever the recursive call returns.

Pattern 3: Merge Two Sorted Lists

A fundamental operation that shows up in many problems.

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy

while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

current.next = l1 or l2
    return dummy.next

Compare the heads of both lists. Append the smaller one. Advance. When one list runs out, append the remaining part of the other.

The dummy head technique (covered below) makes this clean — no special case for the first node.

Problem: Merge K Sorted Lists

Merge k sorted linked lists. The naive approach merges pairs one by one: O(kN). The optimal approach uses a min-heap:

import heapq

def merge_k_lists(lists):
    dummy = ListNode(0)
    current = dummy
    heap = []

for i, l in enumerate(lists):
        if l:
            heapq.heappush(heap, (l.val, i, l))

while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

return dummy.next

O(N log k) where N is the total number of nodes. The heap always has at most k elements.

Alternatively, use divide-and-conquer: merge pairs of lists, then merge the results, and so on. This is also O(N log k) and is essentially merge sort's merge step.

Pattern 4: Dummy Head Technique

A dummy node (also called a sentinel) placed before the head simplifies edge cases where the head itself might change.

Without a dummy head, you need special cases for:

• Inserting at the beginning


• Deleting the head


• Building a new list from scratch

With a dummy head:

dummy = ListNode(0)
dummy.next = head
# ... do operations ...
return dummy.next  # the real head

The dummy node is never part of the final list. dummy.next is always the real head, even if the head changed during the operation.

Problem: Remove All Nodes With Value

def remove_elements(head, val):
    dummy = ListNode(0, head)
    current = dummy

while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next

return dummy.next

Without the dummy, removing the head node requires separate logic. With the dummy, every node (including the original head) is handled uniformly.

Problem: Partition List

Rearrange so all nodes less than x come before nodes >= x, preserving relative order.

def partition(head, x):
    before_dummy = ListNode(0)
    after_dummy = ListNode(0)
    before = before_dummy
    after = after_dummy

while head:
        if head.val < x:
            before.next = head
            before = before.next
        else:
            after.next = head
            after = after.next
        head = head.next

after.next = None        # important: prevent cycle
    before.next = after_dummy.next
    return before_dummy.next

Two dummy heads, two lists. Walk the original list and distribute nodes. Stitch together at the end. The after.next = None line is critical — without it, the last node in the "after" list might still point to a node in the "before" list, creating a cycle.

Pattern 5: In-Place Operations

Many linked list problems require O(1) space, meaning you modify the existing list rather than creating a new one.

Problem: Reorder List

Given 1->2->3->4->5, reorder to 1->5->2->4->3.

This combines three patterns: find middle, reverse second half, merge alternating.

def reorder_list(head):
    if not head or not head.next:
        return

# find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

# reverse second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

# merge alternating
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Problem: Sort a Linked List

Merge sort on a linked list, O(n log n) time, O(1) space (ignoring recursion stack):

def sort_list(head):
    if not head or not head.next:
        return head

# find middle (use slow-fast to split)
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

mid = slow.next
    slow.next = None

# sort each half
    left = sort_list(head)
    right = sort_list(mid)

# merge
    return merge_two_lists(left, right)

Problem: Swap Nodes in Pairs

Swap every two adjacent nodes.

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy

while prev.next and prev.next.next:
        first = prev.next
        second = prev.next.next

first.next = second.next
        second.next = first
        prev.next = second

prev = first

return dummy.next

Common Mistakes

Losing the reference to the next node. Before modifying current.next, save current.next in a variable. This is the single most common bug in linked list problems. Not handling null pointers. Always check if a node is None before accessing .next or .val. Edge cases: empty list, single-node list, two-node list. Forgetting to break the old link. When splitting a list into two halves, set slow.next = None to actually separate them. Without this, you haven't split anything — you've just found the midpoint. Not using a dummy head when you should. If the head might change (removal, insertion, merge), use a dummy. It costs one extra node and saves you from subtle bugs. Creating accidental cycles. When rearranging nodes, make sure the last node's next is None. A cycle will cause infinite loops in any traversal. Drawing it out on paper is not optional. Linked list problems are visual. If you're trying to manipulate pointers purely in your head, you will make mistakes. Draw the nodes, draw the arrows, trace through your code step by step.

Practice Problems

Fast/Slow pointer: Linked List Cycle, Linked List Cycle II, Middle of Linked List, Palindrome Linked List, Remove Nth Node From End Reversal: Reverse Linked List, Reverse Linked List II, Reverse Nodes in K-Group, Swap Nodes in Pairs Merge: Merge Two Sorted Lists, Merge K Sorted Lists, Sort List Dummy head / In-place: Remove Linked List Elements, Partition List, Reorder List, Odd Even Linked List, Remove Duplicates from Sorted List II

Practice these patterns on CodeUp — linked list problems are all about muscle memory with pointer manipulation, and that only comes from writing the code yourself.