Linked List Interview Questions in Python: Reverse, Cycle Detection, Merge and More

Linked lists are small, which is why bugs hide in them: one pointer assigned in the wrong order and half the list is gone. Five problems cover most of what interviewers ask, and they reuse just three ideas: a dummy node, fast and slow pointers, and saving next before you overwrite it. Each problem below has tested Python code and a short note on why it works.

The node class

A singly linked list is a chain of nodes. Each node stores a value and a reference to the next node. The last node points to None.

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

Unlike an array, you cannot jump to the middle in constant time. Reaching the k-th element takes k steps, so most problems are solved by walking the list once with one or more pointers.

Problem 1: reverse a linked list

Given the head of a list, reverse it and return the new head. The standard solution walks through the list and flips each pointer to face backwards.

def reverse_list(head):
    prev = None
    while head:
        nxt = head.next      # remember the rest of the list
        head.next = prev     # flip the pointer
        prev = head          # move prev forward
        head = nxt           # move head forward
    return prev

Take the list 1, 2, 3. Start with prev = None. Step one makes node 1 point to None, step two makes node 2 point to node 1, and step three makes node 3 point to node 2. When head becomes None, prev is node 3, the new head. The key line is saving head.next before changing it, otherwise the rest of the list is lost. The time is O(n) and the space is O(1).

Problem 2: detect a cycle

Does the list loop back on itself? A set of visited nodes works but uses O(n) memory. Floyd’s tortoise and hare algorithm uses O(1) memory: move one pointer one step at a time and another two steps at a time. If there is a cycle, the fast pointer eventually catches up to the slow one inside the loop.

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

If there is no cycle, the fast pointer reaches the end and the loop stops. The condition fast and fast.next protects against errors on lists with an even or odd number of nodes. The time is O(n) and the space is O(1).

Problem 3: find the middle node

The same fast and slow idea finds the middle without counting the length first. When the fast pointer reaches the end, the slow pointer is at the middle.

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

For a list with an even number of nodes, this returns the second of the two middle nodes, which is what LeetCode expects. This helper is a building block for harder problems such as Palindrome Linked List and Reorder List.

Problem 4: merge two sorted lists

Combine two sorted lists into one sorted list. The trick is a dummy node: a placeholder at the start that removes special cases for the head of the result.

def merge_two_lists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b          # attach whatever is left
    return dummy.next

At each step we attach the smaller front node to the result and advance that list. When one list is empty, the remaining nodes of the other are already sorted, so we attach them in one move. The time is O(a + b), where a and b are the lengths, and the space is O(1) because we reuse the existing nodes.

Problem 5: remove the nth node from the end

You cannot count backwards in a singly linked list, so use two pointers with a gap. Move the fast pointer n steps ahead, then move both pointers together. When the fast pointer reaches the last node, the slow pointer sits just before the node to remove.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

The dummy node makes removing the head work without a special case. This is a single pass, so the time is O(n) and the space is O(1).

Patterns to remember

• Dummy node: use it whenever the head of the result might change.
• Fast and slow pointers: middle, cycle detection and the nth node from the end.
• Save before you overwrite: store node.next before you change it.
• Draw it: sketch three or four nodes and update arrows step by step.

Reversal traced one pointer at a time

Reversing a list is the problem where the order of assignments matters most, so it pays to see the state after every step. Here is the iterative version on 1 → 2 → 3, where prev starts as None and curr starts at the head.

When the loop ends, curr has fallen off the list and prev is the new head. Inside each step, the order is always the same: save curr.next first, point curr backwards, then advance both pointers. Skip the save and the rest of the list is gone the moment you overwrite the link.

Five inputs to run before you say you are finished

1. An empty list. Reversal should return None, and cycle detection should return false without touching fast.next.
2. A single node. Many loops that work for three nodes fail here.
3. Two nodes. This is the smallest case where pointer order can go wrong.
4. Removing the n-th node from the end when n equals the length. The head itself has to go, which is exactly what the dummy node is for.
5. A list whose tail points back to the head. Cycle detection must still stop.

These problems also lead elsewhere. Merge k Sorted Lists is really a job for a heap, the fast and slow pointers are cousins of two pointers, and stack questions such as Next Greater Node lead to the monotonic stack.