Linked Lists

class Node:
    __slots__ = ('val', 'next')  # Save memory by avoiding __dict__

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


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

    def insert_head(self, val):
        # New node points to current head, then becomes head
        # Order matters — point first, then update head
        self.head = Node(val, self.head)
        self.size += 1

    def insert_tail(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
        else:
            # Walk to the end — this is why a tail pointer helps
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = new_node
        self.size += 1

    def delete(self, val):
        # Dummy head avoids special-casing deletion of the first node
        dummy = Node(0, self.head)
        prev, curr = dummy, self.head
        while curr:
            if curr.val == val:
                prev.next = curr.next  # Bypass the deleted node
                self.size -= 1
                self.head = dummy.next  # Head might have changed
                return True
            prev, curr = curr, curr.next
        return False

    def find(self, val):
        curr = self.head
        while curr:
            if curr.val == val:
                return curr
            curr = curr.next
        return None

    def to_list(self):
        result, curr = [], self.head
        while curr:
            result.append(curr.val)
            curr = curr.next
        return result

    def reverse(self):
        """Reverse the list in-place by flipping all pointers.
        
        Uses three pointers: prev, curr, next_temp.
        At each step: save next, point curr backward, advance both.
        """
        prev = None
        curr = self.head
        while curr:
            next_temp = curr.next  # Save next before we break the link
            curr.next = prev       # Flip the arrow
            prev = curr            # Advance prev
            curr = next_temp       # Advance curr
        self.head = prev           # prev is now the new head

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  insertHead(val) {
    // Point new node to current head, then swap
    this.head = new ListNode(val, this.head);
    this.size++;
  }

  insertTail(val) {
    const node = new ListNode(val);
    if (!this.head) {
      this.head = node;
    } else {
      let curr = this.head;
      while (curr.next) curr = curr.next;
      curr.next = node;
    }
    this.size++;
  }

  delete(val) {
    // Dummy head pattern — no special case for deleting head
    const dummy = new ListNode(0, this.head);
    let prev = dummy, curr = this.head;
    while (curr) {
      if (curr.val === val) {
        prev.next = curr.next;
        this.head = dummy.next;
        this.size--;
        return true;
      }
      prev = curr;
      curr = curr.next;
    }
    return false;
  }

  find(val) {
    let curr = this.head;
    while (curr) {
      if (curr.val === val) return curr;
      curr = curr.next;
    }
    return null;
  }

  toArray() {
    const result = [];
    let curr = this.head;
    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    return result;
  }
}

class DNode:
    __slots__ = ('val', 'prev', 'next')
    def __init__(self, val, prev=None, nxt=None):
        self.val = val
        self.prev = prev
        self.next = nxt

class DoublyLinkedList:
    def __init__(self):
        # Sentinel nodes eliminate all edge cases
        # head_sentinel <-> ... real nodes ... <-> tail_sentinel
        self.head = DNode(None)
        self.tail = DNode(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def insert_after(self, node, val):
        # Splice new node between node and node.next
        new = DNode(val, node, node.next)
        node.next.prev = new
        node.next = new
        self.size += 1
        return new

    def remove(self, node):
        # Unlink node from both neighbors — O(1) because
        # we have direct access to prev and next
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node.val

    def push_front(self, val):
        return self.insert_after(self.head, val)

    def push_back(self, val):
        return self.insert_after(self.tail.prev, val)

    def pop_front(self):
        if self.size == 0: raise IndexError("empty")
        return self.remove(self.head.next)

    def pop_back(self):
        if self.size == 0: raise IndexError("empty")
        return self.remove(self.tail.prev)

    def move_to_front(self, node):
        """Move an existing node to the front. Used in LRU caches."""
        self.remove(node)
        self.insert_after(self.head, node.val)

def has_cycle(head):
    """Detect if a linked list has a cycle using O(1) space.
    
    Slow pointer moves 1 step, fast pointer moves 2 steps.
    If they meet, there's a cycle. If fast hits None, no cycle.
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head):
    """Find where the cycle begins (if any).
    
    After slow and fast meet inside the cycle, reset one pointer
    to head. Move both one step at a time. They'll meet at the
    cycle's entry point. This works because of a mathematical
    relationship between the distances traveled.
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Reset one pointer to head
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow  # This is the cycle start
    return None  # No cycle

class LRUCache:
    """LRU Cache with O(1) get and O(1) put.
    
    Hash map: key -> node (for instant lookup)
    Doubly linked list: maintains access order
      - Head side = most recently used
      - Tail side = least recently used (eviction candidate)
    """
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> DNode

        # Sentinel nodes (dummy head/tail)
        self.head = DNode(None)
        self.tail = DNode(None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Move to front — this item was just accessed
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = DNode(value)
        node.key = key  # Store key so we can clean up the dict on eviction
        self._add_front(node)
        self.cache[key] = node

        if len(self.cache) > self.capacity:
            # Evict the least recently used (tail side)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node