Linked Lists

Linked List Node

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

Sequential access only, O(1) insert/delete with pointer

The Dummy Head Trick

dummy = ListNode(0, head)
current = dummy
# ... process ...
return dummy.next

Eliminates special cases for head modification

Reversing (Iterative)

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

    while curr:
        next_node = curr.next  # Save
        curr.next = prev       # Reverse
        prev = curr            # Advance prev
        curr = next_node       # Advance curr

    return prev

Reversing (Visual)

1 -> 2 -> 3 -> None

Step 1: None <- 1    2 -> 3
Step 2: None <- 1 <- 2    3
Step 3: None <- 1 <- 2 <- 3

Fast and Slow Pointers

slow = fast = head

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

• Middle: slow is at middle when fast reaches end
• Cycle: if slow == fast, there's a cycle

Cycle Detection (Floyd's)

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Fast laps slow if cycle exists

Merging Sorted Lists

def merge(l1, l2):
    dummy = ListNode()
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    curr.next = l1 or l2
    return dummy.next

LRU Cache Strategy

Combine:

• Hash map: O(1) key lookup
• Doubly linked list: O(1) removal/insertion

Most recent at head, least recent at tail

LRU Operations

Get: Look up in map, move to front

Put:

• If exists: update value, move to front
• If new: add to front, evict tail if over capacity

Common Patterns

Common Mistakes

1. Losing pointers (save next first!)
2. Null pointer access
3. Forgetting dummy head
4. Wrong pointer update order in DLL