Linked List Patterns

Before you can practise any pattern you need a way to make a linked list and a way to read it back as an ordinary Python list so you can eyeball the result. These two helpers do exactly that, and the two class lines define what one node looks like.

1. ListNode is one node of a singly list: it stores a value val and a pointer next to the following node (which starts as None — meaning "nothing after me yet"). DListNode is the doubly version — it also keeps a prev pointer backward.
2. build(vals) turns a normal list like [1,2,3] into a chain. It starts with a throwaway dummy node and a tail that always points at the last real node. For each value it hangs a new node off tail.next, then moves tail onto it — growing the chain one link at a time.
3. It returns dummy.next — the real first node — because the dummy was only scaffolding.
4. to_list(head) walks the chain the other way: start at head, append each head.val, then step forward with head = head.next until head becomes None. That while head: loop is the fundamental way you traverse any linked list.

What the output means: to_list(build([1,2,3])) gives back [1, 2, 3] — proof the chain was built and walked correctly.

Try this: Trace build([9]) by hand: dummy → attach node 9 → return dummy.next, which is the node holding 9. One node, no arrows needed yet.

This deletes every node whose value equals target — even if that's the very first node — without any special "is it the head?" branch. That clean uniformity is exactly what the dummy head buys you.

1. dummy = ListNode(0, head) creates the fake node whose next already points at the real head. prev = dummy starts our "node before the one we're inspecting" right on the dummy.
2. while prev.next: keeps going as long as there's a node after prev to look at. We always inspect prev.next, never prev itself.
3. If prev.next.val == target, we splice it out: prev.next = prev.next.next makes prev skip over the doomed node and point straight at the one after it. The removed node is now unreachable — gone.
4. Otherwise (else) the current node stays, so we advance prev = prev.next. Note we only advance when we don't delete, so consecutive matches all get removed.
5. Finally return dummy.next — the real head, which may itself have changed if the original first node was deleted.

What the output means: For list 1→2→6→3→6 with target=6, you get 1→2→3. Runs in O(n) time, O(1) extra space.

Try this: Set target to the value of the first node. Because of the dummy, deleting the head takes the same line as deleting any other node — no special case.

Three reversals of growing difficulty, all built on the same flip-the-arrow move: reverse the whole list, reverse only a middle section, and reverse in fixed-size groups of k. If you understand part (a), the others are just careful bookkeeping.

1. (a) reverse — prev starts at None (the new tail's "next"). The one dense line head.next, prev, head = prev, head, head.next does all three steps at once: point this node back at prev, move prev onto this node, and step head forward. Python evaluates the right side first, so the old head.next is safely captured before it's overwritten. Return prev — the new head.
2. (b) reverse_between — a dummy head plus a first loop to walk prev to the node just before position left. Then the head-insert trick: repeatedly unhook the node after cur and splice it to the front of the segment, so the segment flips in place while the rest of the list stays attached.
3. (c) reverse_k_group — the helper kth jumps ahead k nodes to check a full group exists; if not kth_node: break stops when fewer than k nodes are left (that tail stays as-is). It reverses each block just like part (a), then re-links the reversed block back into the chain with group_prev.

What the output means: reverse(1→2→3) returns 3→2→1. reverse_between(1→2→3→4→5, 2, 4) gives 1→4→3→2→5. reverse_k_group(1→2→3→4→5, 2) gives 2→1→4→3→5.

Try this: Say the multi-assignment line out loud as three separate statements (save next, flip arrow, advance). Seeing that they happen together is what makes reversal click.

The three fast-slow classics in one place: find the middle, remove the nth node from the end in one pass, and find where a loop begins. All three run two pointers and never precompute the list's length.

1. middle — slow and fast both start at the head; each loop step does slow = slow.next and fast = fast.next.next. The guard while fast and fast.next: stops safely whether the list has an odd or even number of nodes. When it stops, slow is the middle.
2. remove_nth_from_end — first open a gap of n: move fast ahead n nodes. Now advance both until fast is the last node — at that moment slow sits just before the target. slow.next = slow.next.next splices the target out. The dummy head means even "remove the first node" needs no special case.
3. detect_cycle_start (Floyd's algorithm) has two phases. Phase 1: fast and slow race; if the list loops, the fast one laps the slow one and they collide (slow is fast). Phase 2: put a fresh pointer p at the head and advance p and slow together one step at a time — they meet exactly at the node where the loop starts. If fast ever hits None, there's no loop, so return None.

What the output means: On 1→2→3→4→5: middle returns node 3; remove_nth_from_end(...,2) gives 1→2→3→5; detect_cycle_start returns the loop's entry node, or None when the list is straight.

Try this: For middle, draw 4 nodes instead of 5 and step the two pointers by hand — you'll see why while fast and fast.next is the exact stop condition.

Both of these build a brand-new list node-by-node behind a dummy tail — the standard way to assemble a list when you don't know its final length up front.

1. The shared setup dummy = tail = ListNode() makes both names point at the same fake node. tail always marks the end of the list we're growing; dummy stays put so we can return dummy.next at the finish.
2. merge_two — while both input lists have nodes, compare their front values and hook the smaller one onto tail.next, then advance past it. After the loop one list may still have nodes; tail.next = a or b attaches the remaining tail in one shot (a or b gives whichever isn't None).
3. add_two_numbers — the digits are stored reversed, so the ones digit comes first, which is perfect for grade-school addition. Each step adds the two current digits plus a carry; divmod(s, 10) splits the sum into the new carry and the digit to store.
4. The loop condition while a or b or carry is the subtle part: it keeps going until both lists are exhausted and there's no leftover carry — so 99 + 1 = 100 correctly grows an extra digit.

What the output means: merge_two(1→3, 2→4) → 1→2→3→4. add_two_numbers of 2→4→3 (=342) and 5→6→4 (=465) → 7→0→8 (=807).

Try this: Remove the or carry from the second loop and add 9→9 to 1. You'll drop the leading 1 of 100 — that's why the carry belongs in the condition.

Two "composite" problems that prove the earlier patterns were worth learning: each one is just find the middle + reverse the second half, then either compare (palindrome) or interleave (reorder).

1. is_palindrome, step 1: the fast/slow loop walks slow to the middle while fast runs to the end.
2. Step 2: while slow: reverses the second half in place using the same three-way assignment as the whole-list reversal — prev ends up as the head of the reversed back half.
3. Step 3: walk prev (reversed back half) and head (front half) together; if any pair of values differs, return False. If they all match, it's a palindrome.
4. reorder weaves the list into L0→Ln→L1→Ln-1→…. It does the same find-middle + reverse-second-half, then interleaves: alternately pull one node from the front half and one from the reversed back half, splicing them together. The guard if not head or not head.next: return handles empty or single-node lists so the pointer math never crashes.

What the output means: is_palindrome(1→2→2→1) → True; is_palindrome(1→2→3) → False. reorder(1→2→3→4) rewrites the list in place to 1→4→2→3.

Try this: Notice both functions start with the identical fast/slow middle-finder. Composing small proven moves — not memorising a new algorithm — is the real lesson.

The two "scary" ones. Both look like they need extra data structures but fall to a neat pointer trick: find where two lists merge, and deep-copy a list whose nodes also have a random pointer — both in O(1) extra space.

1. get_intersection — start p on list A and q on list B. Each step, when a pointer runs off the end it jumps to the other list's head. That way each walks lenA+lenB nodes, so they line up and meet at the shared node (or both reach None together if the lists never join).
2. copy_random_list, pass 1 — weave a copy after each original node: the chain becomes A→A'→B→B'→…. Now each clone sits right behind its original, so you can find a clone without any lookup table.
3. Pass 2 — wire the clones' random pointers: for each original, its clone's random should point at the clone of the original's random target, which is exactly cur.random.next (the node right after the original's random).
4. Pass 3 — unweave the two interleaved chains back into the original list and a separate cloned list, and return the clone's head. Three linear passes, no hash map.

What the output means: get_intersection returns the first shared node of the two lists, or None. copy_random_list returns a fully independent deep copy — editing it never touches the original.

Try this: For the intersection trick, take two short lists that share a tail and step p and q by hand. Watching each cover lenA+lenB steps is the "aha" that explains why they align without any length math.