Linked List Patterns

1 · The three list types basic

Here's a bug I once spent an afternoon on. A colleague built a task scheduler on a "linked list" he'd cobbled together, and it worked perfectly — until the day he needed to delete a task and its predecessor. His nodes only pointed forward, so to find the node before the one he was holding, he had to re-walk the entire list from the head every single time. What should have been an O(1) delete had quietly become O(n), and under load the scheduler crawled. The fix wasn't cleverer code — it was the right shape of list. That afternoon is why this section exists: before you touch a single pattern, you need to know that a linked list isn't one thing, it's a family, and picking the wrong member is a whole class of pain.

You already met the node in D2 — a little box holding a value and one or more pointers to other boxes. What changes from list to list is purely which arrows each node carries and whether the last node points at nothing or loops home. Think of it like train couplings. A singly linked list is a train where each car is coupled only to the car behind it: you can walk from the engine to the caboose, but never backward, and to reach a car you always start at the front. A doubly linked list couples each car to both neighbours — now you can walk either direction, and if you're standing in a car you can unhook it and rejoin its two neighbours instantly, because you can see both of them. A circular list couples the caboose back to the engine, so the train is a loop with no end — walk forward long enough and you're back where you started.

The common mistake beginners make is reaching for the fanciest option "to be safe" — a doubly linked list everywhere. But every extra pointer is memory you pay for on every node and a second link you must keep correct on every edit; get a prev out of sync with its next and you have a list that walks fine forward and corrupts going backward. Match the shape to the job: singly when you only ever move forward (most interview problems, and the standard ListNode below); doubly when you need O(1) deletion of a node you're already holding or backward traversal (this is exactly why an LRU cache uses one, as you saw in D2); circular for round-robin turns and ring buffers where "after the last comes the first" is the natural rule. Formally: a linked list is a sequence of nodes where each node stores data plus a reference to the next node (and, in a doubly linked list, the previous); the list is identified by a reference to its head, and a null next marks the tail — unless it's circular, in which case the tail's next is the head. The diagram lays all three side by side.

pythonclass ListNode:                       # singly (the classic interview problems standard)
    def __init__(self, val=0, nxt=None):
        self.val, self.next = val, nxt

class DListNode:                      # doubly
    def __init__(self, val=0):
        self.val, self.prev, self.next = val, None, None

# build a list from a Python list, for testing
def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v); tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head: out.append(head.val); head = head.next
    return out

2 · The dummy-head trick essential

Watch what happens the moment "delete this node" includes the possibility of deleting the first one. Your clean little loop — "point the previous node past the one I'm removing" — hits a wall, because the first node has no previous node. So you write an if: "if it's the head, do this special thing; otherwise do the normal thing." Then insertion at the front needs its own special case too. Then a second edge appears, and a third, and your ten-line function is now thirty lines of branching that you have to get right under interview pressure, at 2am, in code review. Nearly every ugly linked-list bug traces back to that one asymmetry: the head has no predecessor.

The dummy-head trick makes the asymmetry vanish. Picture a train again: normally you can't uncouple the engine by "rejoining its neighbours," because it has no car in front of it. So you bolt on a fake lead car — a placeholder that carries no cargo — purely so the real engine now has something ahead of it. Suddenly the engine is just an ordinary car: to remove it, you re-couple the fake car to the second car, exactly the same move you'd use anywhere in the middle. The fake car (the dummy or sentinel) never holds real data and never appears in your answer; it exists only to give the first real node a predecessor so that one code path handles head, middle, and tail identically.

The mechanics are a two-line habit worth burning into muscle memory: at the start, create dummy = ListNode(0, head) so the sentinel points at the current head; do all your work using the dummy as the node "before the front"; then at the very end return dummy.next, not head — because the real head may have changed (you might have deleted or replaced it), and dummy.next always points at whatever the true first node is now. That last part is the common mistake: people build correctly with a dummy and then absent-mindedly return head, handing back a node that's no longer the front. The dummy costs you one throwaway node — O(1) space — and buys you the deletion of an entire category of edge-case branches. It shows up in almost every pattern that follows: remove-nth, merge, partition, remove-duplicates, and the classic below. The diagram shows the sentinel sitting in front of the real list.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def ListNode(*a, **k):  # demo stub
    return _Any()

pythondef remove_elements(head, target):
    dummy = ListNode(0, head)      # sentinel before head
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next   # splice it out — no head special-case
        else:
            prev = prev.next
    return dummy.next                # O(n) time, O(1) space

3 · Reversal — whole, sublist, K-group advanced

If there's one linked-list operation an interviewer will ask you to do live, it's this one — and it's where more candidates lose the pointer than anywhere else. The trap is seductive in its simplicity: "reverse the list" sounds like it should be a one-liner, so people dive in and write node.next = prev as the very first move. And in that instant they've cut the rope they were climbing — the pointer to the rest of the list is gone, unrecoverable, and the loop walks off into None. Reversal isn't hard because the idea is hard; it's hard because the order of three tiny steps is unforgiving.

Here's the analogy that makes it stick. Imagine you're crossing a river on stepping stones, and your job is to flip each stone to face backward as you go. If you flip the stone you're standing on before noting where the next one is, you've stranded yourself — you flipped away your own directions forward. So the discipline is: first look ahead and memorise the next stone (nxt = cur.next), then flip the current stone to face back (cur.next = prev), then step forward onto the stone you memorised. You carry exactly three fingers through the list — prev (the last stone you already flipped), cur (the stone under you now), and nxt (the safety rope to the rest of the list). Miss the order and you fall in.

The common mistake, then, is overwriting cur.next before you've saved it — and once you name that mistake out loud, the fix is obvious and permanent: save-first is golden rule #3 from the box at the top of this page. Note the cost, because it's what makes reversal beloved: a single walk down the list flips every arrow, so it's O(n) time, and you only ever hold three pointers no matter how long the list is, so it's O(1) space — you reverse a million-node list without allocating a second list. Formally, in-place reversal re-points each node's successor link to its predecessor in one pass, and the old tail becomes the new head (that's why the whole-list version returns prev, not head). Everything else in this section — reversing just a middle segment (LC 92), or reversing in fixed blocks of K (LC 25) — is this same three-finger move wrapped in extra bookkeeping about where the reversal starts and stops. Get part (a) into your fingers and the rest is careful stitching. The diagram freezes the flip mid-motion.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def ListNode(*a, **k):  # demo stub
    return _Any()

python# (a) Reverse the whole list (classic)
def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next   # flip & advance
    return prev

# (b) Reverse between positions left..right (classic)
def reverse_between(head, left, right):
    dummy = ListNode(0, head); prev = dummy
    for _ in range(left - 1): prev = prev.next   # node before the segment
    cur = prev.next
    for _ in range(right - left):             # head-insert the next node
        nxt = cur.next
        cur.next = nxt.next
        nxt.next = prev.next
        prev.next = nxt
    return dummy.next

# (c) Reverse in groups of k (classic) — reverse each block of k
def reverse_k_group(head, k):
    def kth(node, k):
        while node and k: node = node.next; k -= 1
        return node
    dummy = ListNode(0, head); group_prev = dummy
    while True:
        kth_node = kth(group_prev, k)
        if not kth_node: break          # fewer than k left → stop
        group_next = kth_node.next
        prev, cur = group_next, group_prev.next
        while cur != group_next:              # reverse this block
            cur.next, prev, cur = prev, cur, cur.next
        group_prev.next, group_prev = kth_node, group_prev.next
    return dummy.next

4 · Two-pointer trio: middle, nth-from-end, cycle start advanced

Try to find the middle of a linked list and your first instinct will be the honest, wasteful one: walk the whole list to count the nodes, divide by two, then walk again to that index. It works, it's correct — and it's two passes, and it forces you to store the length. On an array that's fine; on a linked list, where you can't jump to index n/2 anyway, it feels clumsy, and interviewers use "can you do it in one pass?" precisely to see whether you know the trick. There is a trick, and it's one of the most elegant ideas in this whole track.

Picture two runners on a circular track, one jogging and one sprinting at exactly double speed. When the sprinter has covered the full lap, the jogger — moving half as fast — has covered exactly half of it. That's the entire insight: run a slow pointer one node per step and a fast pointer two nodes per step, and the moment fast reaches the end, slow is sitting on the middle. No counting, no second pass, no stored length — the geometry does the arithmetic for you. This "fast and slow pointers" idea (also called the tortoise-and-hare, which you met for cycle detection in D2) is the parent pattern; the trio in this section are three of its children.

The same two-pointer chassis, retuned, solves two more classics. For nth-from-the-end, don't change the speeds — change the offset: send one pointer n nodes ahead, then walk both at the same pace; when the leader hits the end, the trailer is parked exactly n nodes from the tail, again in one pass. For finding where a cycle begins, you run tortoise-and-hare until they collide inside the loop, then do a second short walk from the head — Floyd's two-phase algorithm, whose "why does the second walk land on the entrance?" is a favourite follow-up (the distance-equality reason is in the note after the lab). The common mistake across all three is the stop condition: writing while fast: instead of while fast and fast.next: will crash with an AttributeError on even-length lists, because fast.next.next dereferences None. Guard both fast and fast.next before you take the double step, every time. All three are O(n) time and O(1) space. The diagram shows the fast/slow pair converging on the middle.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def ListNode(*a, **k):  # demo stub
    return _Any()

pythondef middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n): fast = fast.next   # open a gap of n
    while fast.next:                     # move both until fast is last
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next           # slow is just before the target
    return dummy.next

def detect_cycle_start(head):        # Floyd phase 2
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                # meeting point
            p = head
            while p is not slow:         # both advance 1 → meet at cycle start
                p, slow = p.next, slow.next
            return p
    return None

5 · Merge & add — two sorted lists, add two numbers intermediate → advanced

Up to now every pattern has rearranged an existing list. This section is about the opposite skill: growing a brand-new list one node at a time when you don't yet know how long it will be. That "don't know the length" part is exactly what makes it awkward. With an array you'd pre-size a buffer or just append and let it grow; with a linked list you're holding a chain by its head, and to add to the end you'd normally have to walk all the way to the tail each time — turning a simple build into a hidden O(n²). The fix is a pattern you already have in hand.

Think of it like laying railway track ahead of a moving train. You keep a tail pointer that always sits on the last piece of track you've laid; each new node clicks onto tail.next, and then you slide tail forward onto it. Because you never search for the end — you always know where it is — every attach is O(1), and building an n-node result is a clean O(n). And where does the track start? Behind a dummy head (section 2 again): dummy = tail = ListNode() gives you a stable anchor to hang the first real node off, so even "the very first output node" needs no special case. This dummy-tail construction is the bread-and-butter of list building, and once you see it in merge_two you'll recognise it everywhere.

The two problems here share that skeleton but differ in the interesting details. Merging two sorted lists (LC 21) is the merge step of merge sort you met in D6, done on links instead of array slots: repeatedly bite off the smaller of the two front nodes, and when one list runs dry, tail.next = a or b attaches the entire remaining tail in a single move — no need to copy it node by node. Adding two numbers (LC 2) stores digits in reverse order, which is a gift, not a nuisance: the ones digit comes first, so you add left-to-right exactly like grade-school arithmetic, propagating a carry. The classic mistake there is the loop condition — people write while a and b and lose the final carry, so 99 + 1 produces 00 instead of 100. The correct guard is while a or b or carry: keep going until both lists are exhausted and no carry is left over. The lab builds both behind the same dummy tail.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def ListNode(*a, **k):  # demo stub
    return _Any()

python# (a) Merge two sorted lists (classic)
def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else: tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b                # attach the remaining tail
    return dummy.next

# (b) Add two numbers stored in reverse (classic)
def add_two_numbers(a, b):
    dummy = tail = ListNode(); carry = 0
    while a or b or carry:
        s = carry + (a.val if a else 0) + (b.val if b else 0)
        carry, digit = divmod(s, 10)
        tail.next = ListNode(digit); tail = tail.next
        a = a.next if a else None
        b = b.next if b else None
    return dummy.next

6 · Palindrome & reorder — combine the tools expert expert

"Is this list a palindrome?" is where a lot of people quietly cheat — and the interviewer is watching for it. The easy answer is to copy every value into a Python list and check whether it reads the same forwards and backwards. It's correct, it's fast to write, and it earns a raised eyebrow, because it spends O(n) extra memory to sidestep the actual linked-list challenge. The whole point of the question is: can you do it in place, touching only pointers, in O(1) space? And here's the beautiful part — you already know every move required. You just have to see that the problem is a composite of pieces you've already mastered.

Here's the reframe that unlocks it. To check a palindrome without a copy, split the list at its middle and reverse the back half in place, so now you have two half-length chains pointing at each other from the centre; then walk one finger outward-from-the-middle through each half in lockstep, comparing values. If every pair matches, it's a palindrome. Notice what just happened: "find the middle" is the fast/slow trick from section 4, and "reverse the back half" is the three-finger flip from section 3. You didn't learn a new algorithm — you snapped two old ones together. That is the real lesson of this section, and it's the mindset shift that separates people who memorise fifty problems from people who understand the six primitives that generate them.

Reorder (LC 143), which rewrites L0→L1→…→Ln into the woven L0→Ln→L1→Ln-1→…, is the same recipe with a different final step: find middle, reverse the second half, then instead of comparing the halves you interleave them — pull one node from the front, one from the reversed back, one from the front, and so on. Both are staple Meta/Amazon interview questions precisely because they reward composition over memorisation. The common mistake in both is skipping the guard for tiny inputs: an empty or single-node list has no meaningful "second half," and the pointer arithmetic (fast.next.next, slow.next) will crash on it — so both functions bail early with if not head or not head.next: return. Because the reversal is in place and you only ever hold a fixed handful of pointers, the whole thing stays O(n) time and O(1) space — the exact win the naive copy throws away. The diagram shows the split-reverse-compare dance.

pythondef is_palindrome(head):
    slow = fast = head
    while fast and fast.next:            # slow → middle
        slow, fast = slow.next, fast.next.next
    prev = None                            # reverse second half
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    while prev:                            # compare halves
        if prev.val != head.val: return False
        prev, head = prev.next, head.next
    return True

def reorder(head):                       # L0→Ln→L1→Ln-1→…
    if not head or not head.next: return
    slow = fast = head                     # 1. find middle
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    second = slow.next; slow.next = None   # 2. split
    prev = None                            # 3. reverse second half
    while second:
        second.next, prev, second = prev, second, second.next
    first, second = head, prev             # 4. interleave
    while second:
        first.next, first = second, first.next
        second.next, second = first, second.next

7 · The hard ones — intersection & copy-with-random-pointer expert expert

These are the two problems that make people panic in interviews — and both panics come from the same place: reaching straight for a hash map. "Where do two lists merge?" → your gut says "throw all of list A's nodes in a set, then scan B looking for the first one that's already in the set." "Deep-copy a list whose nodes each have a random extra pointer to anywhere?" → your gut says "map each original node to its clone in a dictionary, then do a second pass wiring up the random links." Both hash-map answers are correct and completely reasonable to state — but each spends O(n) extra memory, and the follow-up question, every time, is "now do it in O(1) space." That follow-up is the whole game, and both have a startlingly clean pointer trick hiding behind the scary description.

For intersection (LC 160), the obstacle is that the two lists can be different lengths, so their shared tail doesn't line up if you naively walk them in parallel. The trick erases the length difference with a tiny sleight of hand: walk pointer p down list A and, when it falls off the end, redirect it to the head of list B; walk q down B and redirect it to A. Each pointer now travels lenA + lenB nodes total — the same distance — so they arrive at the shared node in the very same step (or both hit None together if the lists never join). It's the "swap tracks at the end so both trains run equal total distance" idea; no length math, no set.

For copy-with-random-pointer (LC 138), the difficulty is that a clone's random pointer must point at the clone of some arbitrary node — but during a single pass those clones don't exist yet, which is exactly why the naive solution needs a dictionary to remember "original → clone." The trick sidesteps the dictionary by weaving each new clone directly behind its original: the chain temporarily becomes A→A'→B→B'→…, so a node's clone is always simply node.next — the map is baked into the list's own structure. Then a clone's random is just cur.random.next, and a final pass un-weaves the two chains apart. The common mistake in both is over-engineering: writing the hash-map version and stopping, when the elegant O(1) trick is what's actually being tested. Both run in O(n) time and, thanks to the tricks, O(1) extra space. The lab shows both, and the tip below re-derives why intersection's swap-heads is guaranteed to align.

class _Any:
    '''stands in for any undefined demo value; supports call/attr/index/
    iteration and basic arithmetic (as 0.7) so demo snippets run.'''
    def __call__(self, *a, **k): return _Any()
    def __getattr__(self, k): return _Any()
    def __getitem__(self, k): return _Any()
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __contains__(self, o): return True
    def __enter__(self, *a): return _Any()
    def __exit__(self, *a): return False
    def __float__(self): return 0.7
    def __int__(self): return 1
    def __lt__(self, o): return True
    def __gt__(self, o): return False
    def __le__(self, o): return True
    def __ge__(self, o): return False
    def __add__(self, o): return o
    def __radd__(self, o): return o
    def __bool__(self): return True
    def __repr__(self): return 'demo'
    def __str__(self): return 'demo'
def Node(*a, **k):  # demo stub
    return _Any()

python# (a) Intersection (classic) — two pointers that swap heads at the end
def get_intersection(a, b):
    p, q = a, b
    while p is not q:                    # each walks lenA+lenB, so they align
        p = p.next if p else b
        q = q.next if q else a
    return p                          # the shared node, or None

# (b) Copy list with random pointer (classic) — interleave clones, O(1) space
def copy_random_list(head):
    if not head: return None
    cur = head                        # 1. weave copy after each original: A→A'→B→B'
    while cur:
        cur.next = Node(cur.val, cur.next); cur = cur.next.next
    cur = head                        # 2. wire clones' random pointers
    while cur:
        if cur.random: cur.next.random = cur.random.next
        cur = cur.next.next
    # 3. unweave the two lists
    cur = head; copy_head = head.next
    while cur:
        clone = cur.next
        cur.next = clone.next
        clone.next = clone.next.next if clone.next else None
        cur = cur.next
    return copy_head

Linked-list pattern cheat-sheet expert

Checkpoint expert

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def build(values):                     # O(n)
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):                     # O(n)
    out = []
    while head:
        out.append(head.val); head = head.next
    return out

print(to_list(build([1, 2, 3])))       # [1, 2, 3]

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def reverse(head):                     # O(n) time, O(1) space
    prev = None
    while head:
        nxt = head.next                # save next
        head.next = prev               # flip the pointer
        prev = head                    # advance prev
        head = nxt                     # advance head
    return prev                        # new head

# build 1->2->3, reverse, read back
h = Node(1, Node(2, Node(3)))
r = reverse(h)
out = []
while r: out.append(r.val); r = r.next
print(out)                             # [3, 2, 1]

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def middle(head):                      # slow moves 1, fast moves 2
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
    return slow.val

def nth_from_end(head, n):             # lead pointer starts n ahead
    lead = head
    for _ in range(n):
        lead = lead.next
    trail = head
    while lead:
        lead = lead.next; trail = trail.next
    return trail.val

h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
print(middle(h))          # 3
print(nth_from_end(h, 2)) # 4

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def merge(a, b):                       # O(n + m)
    dummy = tail = Node(0)             # dummy head removes edge cases
    while a and b:
        if a.val <= b.val:
            tail.next = a; a = a.next
        else:
            tail.next = b; b = b.next
        tail = tail.next
    tail.next = a or b                 # attach the remainder
    return dummy.next

a = Node(1, Node(3, Node(5)))
b = Node(2, Node(4, Node(6)))
out, m = [], merge(a, b)
while m: out.append(m.val); m = m.next
print(out)                             # [1, 2, 3, 4, 5, 6]

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def reverse_k_group(head, k):          # O(n) time, O(1) space
    # check there are at least k nodes left
    node, count = head, 0
    while node and count < k:
        node = node.next; count += 1
    if count < k:
        return head                    # fewer than k -> leave as-is
    # reverse this group; `node` is head of the next group
    prev = reverse_k_group(node, k)
    cur = head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur; cur = nxt
    return prev                        # new head of this group

h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
r = reverse_k_group(h, 2); out = []
while r: out.append(r.val); r = r.next
print(out)                             # [2, 1, 4, 3, 5]

class Node:
    def __init__(self, val): self.val = val; self.next = None

def cycle_start(head):                 # O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:          # phase 1: find a meeting point
        slow = slow.next; fast = fast.next.next
        if slow is fast:
            break
    else:
        return None                    # no cycle
    slow = head                        # phase 2: walk both at speed 1
    while slow is not fast:            # they meet at the cycle entrance
        slow = slow.next; fast = fast.next
    return slow

a, b, c, d = Node(1), Node(2), Node(3), Node(4)
a.next, b.next, c.next, d.next = b, c, d, b   # tail loops back to b
print(cycle_start(a).val)              # 2

Knowledge check check yourself