Linked List

How it works

A linked list gives you no random access, so every algorithm is a walk. The work is in rewiring next pointers in an order that never loses the rest of the list. Before you overwrite a pointer, save what it pointed to.

A dummy head is the cheapest trick in the pattern. It gives the real head a predecessor, so deleting or inserting at the front looks exactly like doing it in the middle. Return dummy.next at the end.

Fast and slow pointers find structure without extra memory. When the fast pointer moves two steps for each step of the slow one, the slow pointer is at the middle when the fast one reaches the end, and the two meet inside a cycle if one exists. A gap of k nodes between two pointers finds the k-th node from the end.

Many medium problems are compositions of three primitives: find the middle, reverse a sublist, merge two lists. Reorder, palindrome check and k-group reversal are all built from them.

How to attack it

1. 1Draw three or four nodes and the pointers before writing code.
2. 2Add a dummy head if the head itself might change.
3. 3Save next before overwriting any pointer.
4. 4Break the problem into find-middle, reverse and merge if it looks complicated.
5. 5Test with an empty list, one node, and two nodes.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

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


def reverse(head):
    prev = None
    while head:
        nxt = head.next      # save the rest before rewiring
        head.next = prev
        prev, head = head, nxt
    return prev


def middle(head):
    # Slow ends at the middle (second middle for even lengths).
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def remove_value(head, val):
    dummy = ListNode(0, head)  # gives the head a predecessor
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

What it costs