补充题

K个一组反转链表

每次先检查剩余节点是否够 k 个，不够则保持原样；够的话，用头插法反转 k 个节点，然后移动指针继续处理下一组。时间 O(n)，空间 O(1)。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        while (true) {
            // 检查剩余节点是否够 k 个
            ListNode check = prev;
            for (int i = 0; i < k; i++) {
                check = check.next;
                if (check == null) return dummy.next;
            }

            // 反转 k 个节点
            ListNode curr = prev.next;
            ListNode next;
            ListNode tail = curr;

            for (int i = 0; i < k; i++) {
                next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
                curr = next;
            }
            tail.next = curr;
            prev = tail;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

二叉树序列化与反序列化

序列化用前序遍历，空节点用 "null" 标记；反序列化时按同样的前序顺序从队列中取值递归构建。时间 O(n)，空间 O(n)。

public class Codec {
    // 序列化：前序遍历，用 "null" 表示空节点
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    // 反序列化
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(queue);
    }

    private TreeNode deserializeHelper(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals("null")) return null;

        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(queue);
        node.right = deserializeHelper(queue);
        return node;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

设计支持 O(1) 获取最小值的栈

用两个栈，stack 存数据，minStack 存当前最小值。每次 push 时，如果新值 ≤ minStack 栈顶，就同时压入 minStack；pop 时，如果弹出的值等于 minStack 栈顶，minStack 也弹出。所有操作均为 O(1)。

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);
        // minStack 栈顶始终保存当前栈中的最小值
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        // 如果弹出的值等于当前最小值，minStack 也要弹出
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}