Linked List（鏈結串列）

# python
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

// java

// Single Linkedlist

public class ListNode{

    // attr
    public int val;
    public ListNode next;

    // constructor
    public ListNode(){

    }

    public ListNode(int val){
        this.val = val;
    }

    ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }

}

// init a ListNode
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

// motify node's value
node1.val = 0;

// connect nodes
node1.next = node2;
node2.next = node3;

// java

// Double linked list

// LC 146

public class Node {
    int key;
    int val;
    Node prev;
    Node next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

# python
# LC 206 - Reverse Linked List
# IDEA: walk once; at each node cache next, flip the link back to prev, advance both
# time = O(n), space = O(1)
class Solution(object):
    def reverseList(self, head):
        prev = None              # head of the reversed part (empty at first)
        curr = head              # head of the part not yet reversed
        while curr:
            nxt = curr.next      # 1) cache next: the flip below overwrites it
            curr.next = prev     # 2) flip the link
            prev = curr          # 3) advance prev
            curr = nxt           # 4) advance curr
        return prev              # curr is None, so prev is the old tail = new head

// java
// LC 206 - Reverse Linked List
// IDEA: walk once; at each node cache next, flip the link back to prev, advance both
// time = O(n), space = O(1)
public ListNode reverseList(ListNode head) {
    ListNode prev = null;        // head of the reversed part
    ListNode curr = head;        // head of the part not yet reversed
    while (curr != null) {
        ListNode next = curr.next;   // 1) cache next
        curr.next = prev;            // 2) flip the link
        prev = curr;                 // 3) advance prev
        curr = next;                 // 4) advance curr
    }
    return prev;                 // the old tail is the new head
}

1 -> 2 -> 3
step  prev        curr   reversed part
0     None        1      (empty)
1     1           2      1
2     2 -> 1      3      2 -> 1
3     3 -> 2 -> 1 None   return prev

# python
# LC 206 - Reverse Linked List (recursive)
# IDEA: reverse the rest first; head.next is then the rest's tail, so hang head after it
# time = O(n), space = O(n)   call stack
class Solution(object):
    def reverseList(self, head):
        if head is None or head.next is None:   # empty, or the last node: already reversed
            return head
        new_head = self.reverseList(head.next)  # the original last node, passed up unchanged
        head.next.next = head                   # the node after head now points back at it
        head.next = None                        # cut the old forward link, or 2 nodes form a cycle
        return new_head

// java
// LC 206 - Reverse Linked List (recursive)
// IDEA: recurse to the tail, then let each frame flip the link BEHIND it on the way back.
//       `newHead` is the original last node and is passed up unchanged.
// time = O(n), space = O(n)   (call stack)
public ListNode reverseList(ListNode head) {
    // base case: empty list, or already at the last node
    if (head == null || head.next == null) {
        return head;
    }
    // reverse everything after `head`; newHead is the tail of the ORIGINAL list
    ListNode newHead = reverseList(head.next);
    // head.next now sits BEHIND head in the reversed list: point it back at head
    head.next.next = head;
    // cut the old forward link, or the two nodes form a 2-cycle
    head.next = null;
    return newHead;
}

# python
# LC 203 - Remove Linked List Elements
# IDEA: dummy before head; look ahead at curr.next; on a match skip it and do NOT advance
# time = O(n), space = O(1)
class Solution(object):
    def removeElements(self, head, val):
        dummy = ListNode(0)
        dummy.next = head
        curr = dummy                       # always the last node known to be kept
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next # skip the match; curr stays, the new next is unchecked
            else:
                curr = curr.next           # next is kept, so move onto it
        return dummy.next                  # the head may have been removed

// java
// LC 203 - Remove Linked List Elements
// IDEA: dummy before head; look ahead at curr.next; on a match skip it and do NOT advance
// time = O(n), space = O(1)
public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode curr = dummy;              // always the last node known to be kept
    while (curr.next != null) {
        if (curr.next.val == val) {
            curr.next = curr.next.next; // skip the match; curr does not move
        } else {
            curr = curr.next;           // no match: move forward
        }
    }
    return dummy.next;
}

Initial: dummy -> 6 -> 6 -> 6 -> 3, curr at dummy

Step 1: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 6 -> 6 -> 3 (curr STAYS at dummy)

Step 2: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 6 -> 3 (curr STAYS at dummy)

Step 3: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 3 (curr STAYS at dummy)

Step 4: curr.next.val = 3 (no match)
  Action: curr = curr.next
  Result: curr moves to node 3

Step 5: curr.next = null, exit loop
Return: dummy.next = [3]

# python
# LC 86 - Partition List
# IDEA: two dummies -> append each node to the tail of its chain, then
#       terminate chain 2 and hang it off chain 1's tail via dummy_2.next
# time = O(n), space = O(1)
class Solution(object):
    def partition(self, head, x):
        dummy_1 = ListNode(0)   # chain 1: values <  x
        dummy_2 = ListNode(0)   # chain 2: values >= x
        p1 = dummy_1            # tail of chain 1
        p2 = dummy_2            # tail of chain 2

        curr = head
        while curr:
            if curr.val < x:
                p1.next = curr
                p1 = p1.next
            else:
                p2.next = curr
                p2 = p2.next
            curr = curr.next

        # terminate chain 2: p2 may still point at a node now in chain 1
        p2.next = None

        # join: dummy_2.next is chain 2's head, so it never has to be tracked
        p1.next = dummy_2.next

        return dummy_1.next

// java
// LC 86 - Partition List
// IDEA: two dummies, one tail per chain; cut chain 2's tail, then join chain 1's tail to it
// time = O(n), space = O(1)
public ListNode partition(ListNode head, int x) {
    ListNode dummy1 = new ListNode(0);   // chain 1: values <  x
    ListNode dummy2 = new ListNode(0);   // chain 2: values >= x
    ListNode p1 = dummy1;
    ListNode p2 = dummy2;

    ListNode curr = head;
    while (curr != null) {
        if (curr.val < x) {
            p1.next = curr;
            p1 = p1.next;
        } else {
            p2.next = curr;
            p2 = p2.next;
        }
        curr = curr.next;
    }

    p2.next = null;            // terminate chain 2, or the result can loop
    p1.next = dummy2.next;     // join: chain 1's tail -> chain 2's head

    return dummy1.next;
}

node  goes to   chain 1 (< 3)        chain 2 (>= 3)
 1    chain 1   d1 -> 1              d2
 4    chain 2   d1 -> 1              d2 -> 4
 3    chain 2   d1 -> 1              d2 -> 4 -> 3
 2    chain 1   d1 -> 1 -> 2         d2 -> 4 -> 3
 5    chain 2   d1 -> 1 -> 2         d2 -> 4 -> 3 -> 5
 2    chain 1   d1 -> 1 -> 2 -> 2    d2 -> 4 -> 3 -> 5
                          ^p1                       ^p2

p2.next = None        5.next was still the last 2 -> cut it
p1.next = d2.next     2 -> 4

d1 -> 1 -> 2 -> 2 -> 4 -> 3 -> 5   return d1.next  =>  [1,2,2,4,3,5]

# python
# LC 92 - Reverse Linked List II
# IDEA: walk prev to the node before `left`, reverse right-left+1 nodes with the helper,
#       then reconnect both boundaries with the three handles it returns
# time = O(n), space = O(1)
class Solution(object):
    def reverseBetween(self, head, left, right):
        dummy = ListNode(0)
        dummy.next = head

        # 1) walk `prev` to the node BEFORE position `left`
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        # 2) reverse (right - left + 1) nodes starting at prev.next
        new_head, new_tail, next_node = self.reverse_helper(prev.next, right - left + 1)

        # 3) reconnect both boundaries
        prev.next = new_head       # front:  prev -> new head of reversed chunk
        new_tail.next = next_node  # back:   old head (now tail) -> rest of list

        return dummy.next

    def reverse_helper(self, head, k):
        """reverse k nodes from head; return (new_head, new_tail, first node after)"""
        prev = None
        curr = head
        while curr and k > 0:
            nxt = curr.next     # 1) cache next
            curr.next = prev    # 2) reverse the link
            prev = curr         # 3) advance prev
            curr = nxt          # 4) advance curr
            k -= 1
        return prev, head, curr

// java
// LC 92 - Reverse Linked List II
// IDEA: walk prev to the node before `left`, reverse right-left+1 nodes in place,
//       then reconnect: prev -> new front, old start (now the tail) -> the node after
// time = O(n), space = O(1)
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode prev = dummy;
    for (int i = 0; i < left - 1; i++) {
        prev = prev.next;               // the node BEFORE the segment
    }

    ListNode start = prev.next;         // becomes the segment's tail
    ListNode reversed = null;           // front of the reversed segment
    ListNode curr = start;
    for (int i = 0; i < right - left + 1; i++) {
        ListNode next = curr.next;
        curr.next = reversed;
        reversed = curr;
        curr = next;
    }
    // curr is now the first node AFTER the segment
    prev.next = reversed;               // front
    start.next = curr;                  // back
    return dummy.next;
}

dummy -> 1 -> 2 -> 3 -> 4 -> 5
              └──── reverse these 3 ────┘

Step 1) walk prev (left-1 = 1 step) to node before segment
   dummy -> 1 -> 2 -> 3 -> 4 -> 5
            ^prev  ^start
                   (start = prev.next = node 2)

Step 2) reverse_helper(start=2, k=3)
   -- reverses links of 2,3,4 in isolation --
   before:   2 -> 3 -> 4 -> 5
   after:    2 <- 3 <- 4      5
             |              |
          new_tail       new_head
   returns:
     new_head  = 4   (was k-th node, now front of chunk)
     new_tail  = 2   (was `start`, now points nowhere yet)
     next_node = 5   (first node after the reversed part)

Step 3) reconnect boundaries
   (C1) prev.next = new_head
        node1.next -> 4
   (C2) new_tail.next = next_node
        node2.next -> 5

Final:
   dummy -> 1 -> 4 -> 3 -> 2 -> 5
                 └── reversed ──┘
   return dummy.next  =>  [1, 4, 3, 2, 5]  ✓

// java
// LC 92 - Reverse Linked List II (recursive)
// IDEA: reverseN(head, n) reverses the first n nodes and reattaches `successor` (node n + 1);
//       reverseBetween shifts the window one node per call until it starts at position 1
// time = O(n), space = O(n)   (call stack)
ListNode successor = null;   // node n + 1, recorded by the base case

ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        successor = head.next;   // the first node after the reversed part
        return head;
    }
    ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;       // the node after head now points back at it
    head.next = successor;       // head is the new tail: reattach the rest
    return last;
}

ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        return reverseN(head, n);
    }
    // for head.next the range is [m - 1, n - 1]
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

# python
# LC 876 - Middle of the Linked List
# IDEA: fast takes two steps per slow step; when fast runs out, slow is at the middle
# time = O(n), space = O(1)
class Solution(object):
    def middleNode(self, head):
        slow = head
        fast = head
        while fast and fast.next:   # fast can take two more steps
            slow = slow.next
            fast = fast.next.next
        return slow                 # even length: the SECOND of the two middles

// java
// LC 876 - Middle of the Linked List
// IDEA: fast takes two steps per slow step; when fast runs out, slow is at the middle
// time = O(n), space = O(1)
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;   // even length: the second middle
}

[1,2,3,4,5]          [1,2,3,4,5,6]
slow fast            slow fast
1    1               1    1
2    3               2    3
3    5   stop        3    5
                     4    None   stop
return 3             return 4  (the second middle)

# python
# LC 2 - Add Two Numbers
# IDEA: walk both lists at once, append the digit sum mod 10 to a dummy-headed result, carry the rest
# time = O(max(m, n)), space = O(1) besides the output
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy                 # last node of the result
        carry = 0
        while l1 or l2 or carry:     # the carry can outlive both lists
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next
            carry = total // 10
            tail.next = ListNode(total % 10)
            tail = tail.next
        return dummy.next

// java
// LC 2 - Add Two Numbers
// IDEA: walk both lists at once, append the digit sum mod 10 to a dummy-headed result, carry the rest
// time = O(max(m, n)), space = O(1) besides the output
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int total = carry;
        if (l1 != null) {
            total += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            total += l2.val;
            l2 = l2.next;
        }
        carry = total / 10;
        tail.next = new ListNode(total % 10);
        tail = tail.next;
    }
    return dummy.next;
}

head(dummy) <-> [LRU] <-> ... <-> [MRU] <-> tail(dummy)

# python
# LC 146 - LRU Cache
# IDEA: map key -> node for O(1) lookup; the doubly linked list holds recency order,
#       MRU just before `tail`, LRU just after `head`. put inserts first, then evicts
#       `head.next` if the map has grown past capacity.
# time = O(1) per get/put, space = O(capacity)
class Node:
    def __init__(self, key=0, val=0):
        self.key = key        # kept so eviction can delete the map entry
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.kv_map = {}  # key -> Node

        # sentinel boundaries: head <-> ... <-> tail
        self.head = Node()  # LRU side
        self.tail = Node()  # MRU side
        self.head.next = self.tail
        self.tail.prev = self.head

    def remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def add_to_tail(self, node):      # insert just before tail (MRU)
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node

    def get(self, key):
        if key not in self.kv_map:
            return -1
        node = self.kv_map[key]
        self.remove(node)
        self.add_to_tail(node)        # move to MRU
        return node.val

    def put(self, key, value):
        # case 1) key exists: update in place, refresh to MRU — never evicts
        if key in self.kv_map:
            node = self.kv_map[key]
            node.val = value
            self.remove(node)
            self.add_to_tail(node)
            return

        # case 2) new key: insert first ...
        node = Node(key, value)
        self.kv_map[key] = node
        self.add_to_tail(node)

        # ... then evict the LRU (the first REAL node, not the dummy) if over capacity
        if len(self.kv_map) > self.capacity:
            lru_node = self.head.next
            self.remove(lru_node)
            del self.kv_map[lru_node.key]

// java
// LC 146 - LRU Cache
// IDEA: map key -> node; a sentinel doubly linked list keeps recency order (MRU before tail).
//       put inserts first, then evicts head.next if the map has grown past capacity.
// time = O(1) per get/put, space = O(capacity)
class LRUCache {
    private static class Node {
        int key;
        int val;
        Node prev;
        Node next;

        Node(int key, int val) {
            this.key = key;   // kept so eviction can delete the map entry
            this.val = val;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // LRU side
    private final Node tail = new Node(0, 0);   // MRU side

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToTail(Node node) {   // insert just before tail (MRU)
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        addToTail(node);                  // move to MRU
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {               // existing key: update and refresh, never evict
            node.val = value;
            remove(node);
            addToTail(node);
            return;
        }
        node = new Node(key, value);
        map.put(key, node);
        addToTail(node);
        if (map.size() > capacity) {      // evict the first REAL node
            Node lru = head.next;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

# python
# LC 146 - LRU Cache (library form)
# IDEA: OrderedDict keeps recency order: move_to_end on every use, popitem(last=False) evicts the oldest
# time = O(1) per get/put, space = O(capacity)
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()           # oldest key first, most recent last

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)          # a read is a use
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)      # an update is a use too
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict the least recently used

// java
// LC 146 - LRU Cache (library form)
// IDEA: LinkedHashMap with accessOrder = true reorders on every get/put; removeEldestEntry evicts
// time = O(1) per get/put, space = O(capacity)
class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);        // true = iterate in access order, not insertion order
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;            // called after every put
    }
}

put(1,1): head <-> [1] <-> tail
put(2,2): head <-> [1] <-> [2] <-> tail
get(1):   head <-> [2] <-> [1] <-> tail          ← 1 moved to MRU, returns 1
put(3,3): head <-> [2] <-> [1] <-> [3] <-> tail  ← size 3 > 2
          evict head.next=[2]
          head <-> [1] <-> [3] <-> tail
get(2):   -1
put(4,4): evict head.next=[1]
          head <-> [3] <-> [4] <-> tail
get(1) = -1, get(3) = 3, get(4) = 4

key_to_node  : key  -> Node(key, val, freq)
freq_to_list : freq -> head(dummy) <-> [LRU] <-> ... <-> [MRU] <-> tail(dummy)
min_freq     : the smallest freq whose list is non-empty

freq 1: head <-> [c] <-> tail                <- min_freq = 1, victim = this list's head.next
freq 2: head <-> [a] <-> [b] <-> tail        <- a is older than b
freq 5: head <-> [d] <-> tail

# python
# LC 460 - LFU Cache
# IDEA: the LRU template, once per frequency. key_to_node finds the node in O(1);
#       freq_to_list[f] is a sentinel doubly linked list of every key seen f times,
#       LRU at head.next and MRU before tail; min_freq names the list the victim is in.
# time = O(1) per get/put, space = O(capacity)
class Node:
    def __init__(self, key=0, val=0, freq=0):
        self.key = key            # for eviction to delete the map entry (as in LRU)
        self.val = val
        self.freq = freq          # and freq, to know which list to unlink from
        self.prev = None
        self.next = None

class DLinkedList:
    """the LRU template's list: sentinel head/tail, O(1) unlink and append"""
    def __init__(self):
        self.head = Node()        # LRU side
        self.tail = Node()        # MRU side
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def add_to_tail(self, node):  # insert just before tail (MRU)
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node
        self.size += 1

    def pop_head(self):           # the LRU node of this frequency
        node = self.head.next
        self.remove(node)
        return node

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_node = {}     # key  -> Node
        self.freq_to_list = {}    # freq -> DLinkedList
        self.min_freq = 0

    def touch(self, node):
        """move node from its freq list to the freq+1 list, keeping min_freq exact"""
        old_list = self.freq_to_list[node.freq]
        old_list.remove(node)
        if old_list.size == 0:
            del self.freq_to_list[node.freq]       # keep the map tidy
            # the minimum list just emptied, and this node is about to land one up
            if self.min_freq == node.freq:
                self.min_freq += 1

        node.freq += 1
        if node.freq not in self.freq_to_list:
            self.freq_to_list[node.freq] = DLinkedList()
        self.freq_to_list[node.freq].add_to_tail(node)

    def get(self, key):
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        self.touch(node)
        return node.val

    def put(self, key, value):
        if self.capacity == 0:
            return

        # case 1) key exists: update in place, count the access — never evicts
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self.touch(node)
            return

        # case 2) new key and the cache is full: evict the LRU node of the least-frequent list
        if len(self.key_to_node) == self.capacity:
            victim_list = self.freq_to_list[self.min_freq]
            victim = victim_list.pop_head()
            del self.key_to_node[victim.key]
            if victim_list.size == 0:
                del self.freq_to_list[self.min_freq]

        # case 3) insert at freq 1 — a brand-new key is the least frequent by definition
        node = Node(key, value, 1)
        self.key_to_node[key] = node
        if 1 not in self.freq_to_list:
            self.freq_to_list[1] = DLinkedList()
        self.freq_to_list[1].add_to_tail(node)
        self.min_freq = 1

put(1,1): f1: [1]                              min_freq=1
put(2,2): f1: [1, 2]                           min_freq=1
get(1):   f1: [2]       f2: [1]                -> 1   f1 still non-empty, min_freq stays 1
put(3,3): full -> evict f1.head.next = [2]
          f1: [3]       f2: [1]                min_freq=1  (reset by the insert)
get(2):   -1
get(3):   f1: []        f2: [1, 3]             -> 3   f1 emptied AND was the min -> min_freq=2
put(4,4): full -> evict f2.head.next = [1]     1 and 3 both have freq 2; 1 is the older
          f1: [4]       f2: [3]                min_freq=1
get(1) = -1, get(3) = 3, get(4) = 4

# python
# LC 460 - LFU Cache (library form)
# IDEA: freq -> OrderedDict of keys (oldest first); min_freq names the bucket the victim lives in
# time = O(1) per get/put, space = O(capacity)
from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_val_freq = {}                    # key -> [value, freq]
        self.freq_to_keys = defaultdict(OrderedDict)  # freq -> keys, least recent first
        self.min_freq = 0

    def touch(self, key):
        value, freq = self.key_to_val_freq[key]
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:                # the minimum bucket just emptied
                self.min_freq += 1
        self.key_to_val_freq[key][1] = freq + 1
        self.freq_to_keys[freq + 1][key] = None      # appended = most recent in its bucket

    def get(self, key):
        if key not in self.key_to_val_freq:
            return -1
        self.touch(key)
        return self.key_to_val_freq[key][0]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.key_to_val_freq:              # update: a touch, never an eviction
            self.key_to_val_freq[key][0] = value
            self.touch(key)
            return
        if len(self.key_to_val_freq) == self.capacity:
            victim, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            if not self.freq_to_keys[self.min_freq]:
                del self.freq_to_keys[self.min_freq]
            del self.key_to_val_freq[victim]
        self.key_to_val_freq[key] = [value, 1]
        self.freq_to_keys[1][key] = None
        self.min_freq = 1