鏈結串列實戰：5 題從讀題推導到最優解（LC 206/21/141/143/146）

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next        # save next before breaking the link
        curr.next = prev       # reverse the pointer
        prev = curr            # advance both
        curr = nxt
    return prev                # prev is the new head

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nxt = curr->next;   // save next
        curr->next = prev;            // reverse
        prev = curr;                  // advance
        curr = nxt;
    }
    return prev;
}

def mergeTwoLists(l1, l2):
    dummy = tail = ListNode(0)        # virtual head kills the edge case
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2              # attach the remaining tail
    return dummy.next

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
        else                    { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;        // attach the rest
    return dummy.next;
}

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # 1 step
        fast = fast.next.next       # 2 steps
        if slow == fast:            # they meet → cycle
            return True
    return False                    # fast hit null → no cycle

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

def reorderList(head):
    # 1. find middle (slow ends at the middle)
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. reverse the second half
    second = slow.next
    slow.next = None                 # cut into two halves
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    # 3. merge the two halves alternately
    first, second = head, prev
    while second:
        f_nxt, s_nxt = first.next, second.next
        first.next = second
        second.next = f_nxt
        first, second = f_nxt, s_nxt

void reorderList(ListNode* head) {
    // 1. find middle
    ListNode* slow = head; ListNode* fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    // 2. reverse second half
    ListNode* second = slow->next;
    slow->next = nullptr;
    ListNode* prev = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev; prev = second; second = nxt;
    }
    // 3. merge alternately
    ListNode* first = head; second = prev;
    while (second) {
        ListNode* fn = first->next; ListNode* sn = second->next;
        first->next = second; second->next = fn;
        first = fn; second = sn;
    }
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()        # ordered = built-in HashMap + DLL
        self.cap = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)       # mark as most recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)   # evict least recently used

class LRUCache {
    int cap;
    list<pair<int,int>> dll;                       // front = most recent
    unordered_map<int, list<pair<int,int>>::iterator> pos;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (pos.find(key) == pos.end()) return -1;
        dll.splice(dll.begin(), dll, pos[key]);    // O(1) move to front
        return pos[key]->second;
    }
    void put(int key, int value) {
        if (pos.count(key)) {
            pos[key]->second = value;
            dll.splice(dll.begin(), dll, pos[key]);
            return;
        }
        if ((int)dll.size() == cap) {
            pos.erase(dll.back().first);            // evict LRU (tail)
            dll.pop_back();
        }
        dll.push_front({key, value});
        pos[key] = dll.begin();
    }
};