Linked Lists

A linked list is a chain of nodes, each pointing to the next. Unlike arrays, you can't jump to the middle - you have to walk node by node. But insertion and deletion? O(1) if you're already at the right spot.

The Mental Model

Think of a linked list like a treasure hunt. Each clue (node) tells you where to find the next one. You can't skip ahead - you follow the chain.

Essential Operations

Reversing a Linked List

The classic. Change each node's next pointer to point backward:

def reverseList(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next  # Save next
        curr.next = prev       # Reverse pointer
        prev = curr            # Move prev forward
        curr = next_node       # Move curr forward

    return prev

Finding the Middle

Use slow and fast pointers. When fast reaches the end, slow is at the middle:

def findMiddle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

The Dummy Node Trick

When you might need to modify the head, use a dummy node. It eliminates edge cases:

def removeElements(head, val):
    dummy = ListNode(0)
    dummy.next = head
    curr = dummy

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

    return dummy.next