Linked List Operations

from __future__ import annotations
from dataclasses import dataclass

@dataclass(slots=True)
class Node:
    value: int
    next: Node | None = None

class SinglyLinkedList:
    def __init__(self):
        self.head: Node | None = None
        self.tail: Node | None = None
        self.size = 0

    def push_front(self, value: int) -> Node:
        fresh = Node(value, self.head)
        self.head = fresh
        if self.tail is None:          # empty -> one node
            self.tail = fresh
        self.size += 1
        return fresh

    def push_back(self, value: int) -> Node:
        fresh = Node(value)
        if self.tail is None:
            self.head = self.tail = fresh
        else:
            self.tail.next = fresh
            self.tail = fresh
        self.size += 1
        return fresh

    def insert_after(self, node: Node, value: int) -> Node:
        fresh = Node(value, node.next)  # preserve suffix first
        node.next = fresh              # publish splice
        if self.tail is node:
            self.tail = fresh
        self.size += 1
        return fresh

    def pop_front(self) -> int:
        if self.head is None:
            raise IndexError("pop from empty list")
        victim = self.head
        self.head = victim.next
        if self.head is None:
            self.tail = None
        victim.next = None
        self.size -= 1
        return victim.value

    def delete_after(self, predecessor: Node) -> int:
        victim = predecessor.next
        if victim is None:
            raise IndexError("no node follows predecessor")
        predecessor.next = victim.next
        if self.tail is victim:
            self.tail = predecessor
        victim.next = None
        self.size -= 1
        return victim.value

import java.util.NoSuchElementException;

final class SinglyLinkedList {
    static final class Node {
        final int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node head;
    private Node tail;
    private int size;

    Node pushFront(int value) {
        Node fresh = new Node(value, head);
        head = fresh;
        if (tail == null) tail = fresh; // empty -> one node
        size++;
        return fresh;
    }

    Node pushBack(int value) {
        Node fresh = new Node(value, null);
        if (tail == null) {
            head = tail = fresh;
        } else {
            tail.next = fresh;
            tail = fresh;
        }
        size++;
        return fresh;
    }

    Node insertAfter(Node node, int value) {
        Node fresh = new Node(value, node.next); // preserve suffix first
        node.next = fresh;                      // publish splice
        if (tail == node) tail = fresh;
        size++;
        return fresh;
    }

    int popFront() {
        if (head == null) throw new NoSuchElementException("pop from empty list");
        Node victim = head;
        head = victim.next;
        if (head == null) tail = null;
        victim.next = null;
        size--;
        return victim.value;
    }

    int deleteAfter(Node predecessor) {
        Node victim = predecessor.next;
        if (victim == null) {
            throw new NoSuchElementException("no node follows predecessor");
        }
        predecessor.next = victim.next;
        if (tail == victim) tail = predecessor;
        victim.next = null;
        size--;
        return victim.value;
    }
}

def reverse(self) -> None:
    old_head = self.head
    prev = None
    current = self.head

    while current is not None:
        successor = current.next  # save before overwrite
        current.next = prev
        prev = current
        current = successor

    self.head = prev
    self.tail = old_head

# Invariant before each iteration:
# - prev reaches the reversed processed prefix
# - current reaches the untouched suffix
# - those disjoint chains contain every original node

final class ReversibleList<T> {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value) { this.value = value; }
    }

    private Node<T> head;
    private Node<T> tail;

    void reverse() {
        Node<T> oldHead = head;
        Node<T> previous = null;
        Node<T> current = head;

        while (current != null) {
            Node<T> successor = current.next; // save before overwrite
            current.next = previous;
            previous = current;
            current = successor;
        }

        head = previous;
        tail = oldHead;
    }
}

// Invariant before each iteration:
// - previous reaches the reversed processed prefix
// - current reaches the untouched suffix
// - those disjoint chains contain every original node

def cycle_entry(head: Node | None) -> Node | None:
    slow = fast = head

    # Phase 1: find a meeting point, if a cycle exists.
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None

    # Phase 2: equal-speed pointers meet at the entry.
    seeker = head
    while seeker is not slow:
        seeker = seeker.next
        slow = slow.next
    return seeker

final class CycleEntry {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value) { this.value = value; }
    }

    static <T> Node<T> find(Node<T> head) {
        Node<T> slow = head;
        Node<T> fast = head;

        // Phase 1: find a meeting point, if a cycle exists.
        do {
            if (fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        // Phase 2: equal-speed pointers meet at the entry.
        Node<T> seeker = head;
        while (seeker != slow) {
            seeker = seeker.next;
            slow = slow.next;
        }
        return seeker;
    }
}