Linked Lists

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt          # a reference to another Node, or None

# Build 7 -> 3 -> 9 -> None, back to front
c = Node(9)
b = Node(3, c)
a = Node(7, b)
head = a

# Traverse. Note: no index anywhere.
cur = head
while cur is not None:
    print(cur.value)
    cur = cur.next

class DNode:
    """A doubly linked node. The extra pointer is what makes the LRU cache
       in Chapter 29 possible."""
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


def delete_singly(head, target):
    """Singly linked: we must track prev ourselves, because a node
       cannot see backwards."""
    if head is None:
        return None
    if head.value == target:
        return head.next
    prev, cur = head, head.next
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next      # route around it
            return head
        prev, cur = cur, cur.next
    return head


def delete_doubly(node):
    """Doubly linked: given only the node itself, O(1). No search, no head."""
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    # Two writes. This is the operation an LRU cache needs a thousand
    # times a second, and it is why the extra pointer earns its keep.

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next        # 1. SAVE the rest of the list  ← do this first
        cur.next = prev       # 2. flip this node's arrow backwards
        prev = cur            # 3. prev moves forward
        cur = nxt             # 4. cur moves forward
    return prev               # prev is the new head

# Swap lines 1 and 2 and the list is destroyed: cur.next now points at
# prev, so `nxt = cur.next` walks backwards and you loop forever over
# two nodes. Try it in the playground — it is a good failure to see once.

def reverse_rec(head):
    if head is None or head.next is None:
        return head                  # base case: 0 or 1 nodes
    new_head = reverse_rec(head.next)  # reverse everything after me
    head.next.next = head              # my successor now points back at me
    head.next = None                   # I become the new tail
    return new_head

# Elegant, and O(n) SPACE — one stack frame per node. On a million-node
# list this raises RecursionError. The iterative version is O(1) space.
# When both exist and one uses less memory, prefer that one.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # `is`, not `==` — identity, not value
            return True
    return False                    # fast ran off the end: no cycle

# O(n) time, O(1) space.
#
# Why it terminates: once both runners are inside the loop, the fast one
# gains exactly one position per step on the slow one. A gap that shrinks
# by one every step and lives on a finite circle must reach zero.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head                 # reset one runner
            while slow is not fast:     # now BOTH move one step
                slow, fast = slow.next, fast.next
            return slow                 # the loop entrance
    return None

# The proof is a short piece of algebra: if the tail before the loop has
# length T and the meeting point is M steps into a loop of length L, then
# the distance from the meeting point back round to the entrance is exactly
# T. So two walkers, one from the head and one from the meeting point,
# moving at the same speed, arrive together.