Linked list basics

Problem

An array gives you any element by index. A linked list gives you the head, and everything else is reached one hop at a time. In exchange, a node can be spliced in or out in constant time once you hold the node before it. Interview problems ask you to reverse a list, merge two, remove a node, add two numbers digit by digit, rotate, or reorder, all in place. They are rarely hard in idea; they are hard because one wrong assignment order silently loses the rest of the list.

Intuition

Picture a train of cars, each coupled only to the car behind it. To reverse the train you can only work at the coupling you are standing at. You uncouple the car in front of you, but first remember which car was behind it, because once the coupling is gone nothing else tells you where the rest of the train is. Reverse the first coupling, step to the remembered car, repeat. That is the whole algorithm: remember, then rewire, then step.

The dummy node is a cheap trick with a big payoff. If the operation might change the head (removing the first node, merging where the second list starts smaller), attach a throwaway node in front and work with "the node before" uniformly. At the end return dummy.next.

The top row is the input. In each row below, blue nodes are the reversed part (newest on the left) and the outlined nodes are what remains. Each row costs one pointer rewrite.

Mechanics

The invariant

For reversal, keep two pointers, prev (the head of the already-reversed part, initially null) and cur (the head of the rest). The invariant: prev heads a correctly reversed list of everything before cur, and cur heads the untouched remainder. One step saves cur.next, points cur.next at prev, then advances both. Each step keeps the invariant and moves one node across, so when cur is null prev heads the whole reversed list.

Dummy head and tail

To build or edit a list from the front, create dummy = Node(0) and a tail that starts at it. To append a node, set tail.next to it and move tail. For merging, the invariant is that everything from dummy.next to tail is the sorted merge of the nodes already consumed. When one list runs out, point tail.next at the other, whole, because the rest of a sorted list is already sorted.

Two pointers with a fixed gap

To remove the nth node from the end in one pass, advance a leader so it is n + 1 steps ahead of the dummy, then move leader and trailer together. When the leader reaches null, the trailer is exactly one node before the one to cut. The dummy covers the case where the cut is the first node, because then the trailer is the dummy itself.

The leader starts n + 1 steps ahead of the trailer and they move in lockstep. At the end the amber node, the one after the trailer, is the one to cut; the leader is off the right edge, at null.

Worked example

Reverse [1, 2, 3, 4, 5]. Each step takes the next node and puts it in front of the reversed part:

The reversed list is 5, 4, 3, 2, 1.

Merge [1, 4, 6, 9] and [2, 3, 7]. Each step compares the two heads and splices the smaller:

The second list is exhausted, so the leftover 9 is attached in a single assignment. The merged list is 1, 2, 3, 4, 6, 7, 9.

Remove the 2nd node from the end of [1, 2, 3, 4, 5]. Positions are indices, with the dummy at −1:

The leader is null and the trailer sits at index 2, so the node after it, holding 4, is cut. The list becomes 1, 2, 3, 5.

Implementation

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


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


def merge(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 the rest whole
    return dummy.next


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


def add_two_numbers(a, b):
    dummy = tail = ListNode()
    carry = 0
    while a or b or carry:
        total = carry + (a.val if a else 0) + (b.val if b else 0)
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
        a = a.next if a else None
        b = b.next if b else None
    return dummy.next

In merge, the tuple assignment tail.next, a = a, a.next evaluates the right side first, so a.next is read before a changes. Reordering such a line is a classic way to lose the rest of a list.

Variations and edge cases

• Reverse part of the list. Walk to the node before position left, then repeatedly move the node after the sublist's first node to the front of the sublist, right − left times.
• Reverse in groups of k. First check that k nodes remain; if so, reverse exactly that block and reconnect it between the previous group's tail and the next group's head. Leave a short final block as is.
• Rotate. Count the length, join the tail to the head to make a ring, and break the ring at length minus (k mod length).
• Swap in pairs. Behind a dummy, rewire two nodes at a time and save the next pair first.
• Recursive reverse. Elegant, but it uses O(n) stack; for lists of 10⁵ nodes it reaches Python's recursion limit.
• Edge cases: an empty list, a single node, removing the head, removing the tail, n equal to the length, unequal list lengths in addition, a final carry that needs one more node, and forgetting to set the last node's next to null (which creates a cycle).

Complexity and tradeoffs

• Time: O(n) for a single pass; each node is touched a constant number of times. Reversal here took 5 rewrites for 5 nodes.
• Space: O(1) for in-place rewiring. Copying values into an array and rebuilding is O(n) space and usually acceptable in practice, but it is not what the problem is testing.
• Baseline. Counting the length first, then walking to position length − n, is two passes and also O(n). The gap trick is one pass for the same asymptotic cost.
• When it fails. Lists have no random access, so binary search and indexing are out. If you need cycles or the middle, the next page's fast and slow pointers apply; if you need O(1) lookup by key along with order, the list design page combines a list with a hash map.

Problems

The home problems are in-place rewiring in its common forms: reversing the whole list or a part of it, in groups, merging, splicing nodes in and out, rotating, and adding numbers digit by digit. Merge k sorted lists, reorder list and palindrome list are listed as "also uses" because they combine these moves with another idea.

Easy

• 21. Merge Two Sorted Lists Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Splice from whichever head is smaller onto a dummy tail, then attach the leftover list in one step.
• 206. Reverse Linked List Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Walk the list keeping a previous pointer and point each node back at it, saving the next node before you overwrite the link.

Medium

• 2. Add Two Numbers Grind 169 NeetCode 150 NeetCode 250
  Walk both lists together like grade-school addition, carrying into the next node and appending a final node if a carry is left.
• 19. Remove Nth Node From End of List Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Advance a lead pointer n steps first, then move both until the lead falls off, leaving the trailer just before the node to cut; a dummy head covers removing the first node.
• 24. Swap Nodes in Pairs Grind 169
  Rewire nodes two at a time behind a dummy head, saving the next pair before you break the links.
• 61. Rotate List Grind 169
  Find the length, connect the tail to the head to make a ring, and cut it at length minus k mod length.
• 92. Reverse Linked List II NeetCode 250
  Stop just before position left, then move each following node to the front of the sublist until position right is reached.
• 148. Sort List Grind 169
  Merge sort suits lists: split at the middle with fast and slow pointers, sort each half, and merge them.
• 328. Odd Even Linked List Grind 169
  Build the odd-position chain and the even-position chain by rewiring in place, then attach the even chain after the odd one.
• 2807. Insert Greatest Common Divisors in Linked List NeetCode 250
  Walk adjacent pairs and splice in a node holding their gcd, then step past the inserted node.

Hard

• 25. Reverse Nodes in k-Group Grind 169 NeetCode 150 NeetCode 250
  Check that k nodes remain, reverse exactly that block, and stitch its new head and tail back between the previous and next groups.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 234. Palindrome Linked List Easy
• 143. Reorder List Medium
• 23. Merge k Sorted Lists Hard

Connections

Linked lists are the simplest recursive structure, so the recursion page is the best companion: a list is either empty or a node followed by a list. The pointer discipline here carries over to trees, where the same "save, rewire, advance" appears in rotations and in flattening.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 10.2: linked lists and sentinels, which are the dummy nodes used here.
• Sedgewick and Wayne, Algorithms, section 1.3: linked-list implementations of bags, queues and stacks, including reversing a list.
• Skiena, The Algorithm Design Manual: the discussion of pointer-based data structures and their tradeoffs against arrays.
• Knuth, The Art of Computer Programming, volume 1, section 2.2: linear lists and the manipulation of links.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.