Linked Lists

🧠 Spot It

Use Linked List patterns when:

1. Problem involves pointer manipulation (reversal, merging, cycle)
2. O(1) space constraint — no converting to array
3. Relative ordering of nodes matters

---

Pattern 1 — Fast & Slow Pointers (Floyd's)

Detect cycles, find midpoint, find kth from end.

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

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at middle

---

Pattern 2 — In-Place Reversal

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

---

Pattern 3 — Merge Two Sorted Lists

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    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

---

Senior Tricks

• Dummy node — always use dummy = ListNode(0); dummy.next = head to avoid edge cases on head removal
• Two-pass trick — first pass to get length, second pass to find target position
• Draw it out — pointer problems are visual; sketch before coding

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->