Linked List 101

What a linked list is and why interviewers love it

Nodes and pointers

A singly linked list is a chain of nodes, each holding a value and a reference to the next node. The last node points to None. There is no indexing: to reach the 5th node you must walk from the head. In return, inserting or removing a node is O(1) once you hold a reference to the node before it, because only pointers change and nothing shifts.

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

Why it shows up so often

Linked list problems rarely need a clever algorithm. They test whether you can change pointers in the right order without losing part of the list. A single wrong assignment (node.next = ... before saving the old node.next) silently drops the rest of the chain. That is why this topic is a favourite for checking care and clarity in both campus and lateral interviews.

Signals in a problem statement

• The input is explicitly a ListNode head.
• "Reverse" the whole list, a section, or groups of k.
• "Merge" sorted lists, or "add two numbers stored as digits".
• "Remove the n-th node from the end", "find the middle".
• "Detect a cycle" or "find where two lists intersect".
• "Reorder", "partition", "rotate" a list.

Mental model

Draw boxes and arrows. For every pointer change, write the before and after picture. Most solutions only need three ideas: a dummy node in front of the head, a reversal loop with prev, cur and nxt, and fast and slow pointers. The next chapter gives a template for each.

Core patterns with templates

1. Dummy head

A dummy node removes the special case of changing the head.

def merge_two(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
    return dummy.next

2. Reverse in place

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

Save nxt first, flip the arrow, then advance both pointers. Example: 1 -> 2 -> 3 becomes 3 -> 2 -> 1.

3. Fast and slow pointers

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

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

4. Gap of n for "n-th from the end"

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

Starting both at the dummy and moving fast ahead n + 1 steps leaves slow just before the node to delete.

5. Digit addition with carry

Walk both lists together, sum the digits plus carry, append total % 10 to a dummy-headed result, and keep carry = total // 10. Continue while either list or the carry remains.

Complexity, mistakes and edge cases

Complexity

Recursion on a linked list uses stack space proportional to its length; for lists of 10⁵ nodes Python's default recursion limit will be exceeded. Prefer iterative solutions and mention why.

Common mistakes

• Losing the rest of the list by overwriting cur.next before saving it.
• Not handling the head changing. Removing or reversing the first node is the classic bug; a dummy node fixes it.
• Null access. fast.next.next fails if fast.next is None; check fast and fast.next.
• Returning the wrong node. After reversal the new head is prev, not cur (which is None).
• Comparing values instead of nodes. For cycle and intersection questions use is, because two different nodes can hold equal values.
• Forgetting the final carry in digit addition (5 + 5 must give 0 -> 1).
• Creating a cycle by accident when relinking, for example forgetting to set the last node's next to None after a partition.

Edge cases

Empty list (head is None), one node, two nodes, n equal to the length (remove the head), lists of different lengths, k larger than the length, and k = 1 (no change).

Testing without a judge

Write two helpers in the interview if time allows: one that builds a list from a Python list, and one that converts a list back to a Python list. Then dry-run each edge case in seconds.

Variations and practise

How interviewers twist it

• Reverse a sublist between positions left and right: walk to the node before left, then repeatedly move the next node to the front of the sublist.
• Reverse in groups of k. Check that k nodes remain, reverse exactly those, connect the previous group's tail to the new group head, and move on. Leave a final short group unchanged. A dummy node and a group_prev pointer keep this clean.
• Find where a cycle starts. After fast and slow meet, move one pointer back to the head and advance both one step at a time; they meet at the cycle start.
• Palindrome list in O(1) space. Find the middle, reverse the second half, compare, and (politely) restore it.
• Merge k sorted lists. Use a heap of the current heads; this links to the Heap card.
• Copy a list with random pointers. Use a map from old node to new node, or interleave copies.
• Doubly linked list plus hash map. This is the classic LRU cache design question.

How to explain it

Before coding, draw three nodes and narrate each pointer change. Interviewers forgive slow typing far more readily than a muddled explanation.

Practise

The problems below start with reversal and merging, then the one-pass removal with a gap, digit addition with carry, and finally reversing in groups of k. For each one, decide up front whether a dummy node will simplify the head case; it almost always will.