5. Linked Lists

Key Insight

Linked list problems almost always use two pointers — either fast/slow (Floyd's cycle) or a trailing pointer for deletion. Because there's no random access, master pointer manipulation patterns rather than algorithmic complexity.

5.1 Node Definition

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

# Build from list (utility)
def build(vals: list[int]) -> ListNode | None:
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

# Convert to list (utility)
def to_list(head: ListNode | None) -> list[int]:
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

---

5.2 Core Templates

# --- Reverse a linked list (iterative) --- O(n)
def reverse(head: ListNode | None) -> ListNode | None:
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

# --- Reverse (recursive) ---
def reverse_rec(head: ListNode | None) -> ListNode | None:
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

# --- Find middle (slow/fast) ---
def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # for even length, returns second middle

# --- Detect cycle (Floyd's) ---
def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# --- Find cycle start ---
def cycle_start(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

# --- Merge two sorted lists ---
def merge_sorted(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1; l1 = l1.next
        else:
            cur.next = l2; l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

# --- Remove Nth from end (one pass) ---
def remove_nth_from_end(head: ListNode, n: int) -> ListNode | None:
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

# --- Reorder list: L0→L1→…→Ln → L0→Ln→L1→Ln-1→… ---
def reorder_list(head: ListNode | None) -> None:
    if not head:
        return
    mid = find_middle(head)
    second = reverse(mid.next)
    mid.next = None
    first = head
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

---

5.3 Key CP Patterns

Problem	Technique
Cycle detection	Floyd's slow/fast
Kth from end	Two pointers, k gap
Palindrome list	Reverse second half
Merge k sorted lists	Heap + dummy head
Intersection of two lists	Length equalization

---