// 第 9 周 – 实践课练习的参考答案
// 运行：java Exercises09.java
public class Exercises09 {

    static class Node {
        int value;
        Node next;
        Node(int v, Node n) { value = v; next = n; }
    }

    static Node fromArray(int... a) {
        Node head = null;
        for (int i = a.length - 1; i >= 0; i--) head = new Node(a[i], head);
        return head;
    }

    static String str(Node h) {
        StringBuilder sb = new StringBuilder("[");
        for (Node p = h; p != null; p = p.next) sb.append(p.value).append(p.next != null ? " " : "");
        return sb.append("]").toString();
    }

    // E1. 遍历一次求元素的和与最大值
    static int[] sumAndMax(Node h) {
        int sum = 0, max = Integer.MIN_VALUE;
        for (Node p = h; p != null; p = p.next) {
            sum += p.value;
            max = Math.max(max, p.value);
        }
        return new int[] { sum, max };
    }

    // E2. 第 i 个元素（从 0 开始）– O(i)，没有直接访问！
    static Integer get(Node h, int i) {
        Node p = h;
        for (int k = 0; k < i && p != null; k++) p = p.next;
        return p == null ? null : p.value;
    }

    // E3. x 出现了多少次？
    static int count(Node h, int x) {
        int c = 0;
        for (Node p = h; p != null; p = p.next) if (p.value == x) c++;
        return c;
    }

    // E4. 通过修改指针原地逆置链表 – O(n),O(1) 空间
    static Node reverse(Node h) {
        Node prev = null, p = h;
        while (p != null) {
            Node next = p.next; // 记住从哪里继续
            p.next = prev;      // 把指针反过来
            prev = p;
            p = next;
        }
        return prev; // 新的表头是原来的最后一个结点
    }

    // E5. 删除所有值为 x 的结点
    static Node removeAll(Node h, int x) {
        while (h != null && h.value == x) h = h.next; // 开头的那些结点
        if (h == null) return null;
        Node p = h;
        while (p.next != null) {
            if (p.next.value == x) p.next = p.next.next;
            else p = p.next;
        }
        return h;
    }

    // E6. 遍历一次找中间结点：“兔子”每次走两步，“乌龟”走一步
    static int middle(Node h) {
        Node slow = h, fast = h;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.value;
    }

    // E7. 有序插入：链表保持递增顺序
    static Node insertSorted(Node h, int x) {
        if (h == null || x <= h.value) return new Node(x, h);
        Node p = h;
        while (p.next != null && p.next.value < x) p = p.next;
        p.next = new Node(x, p.next);
        return h;
    }

    public static void main(String[] args) {
        Node h = fromArray(4, 9, 2, 9, 7);
        int[] sm = sumAndMax(h);
        System.out.println("E1. list " + str(h) + ": sum = " + sm[0] + ", max = " + sm[1]);
        System.out.println("E2. get(3) = " + get(h, 3) + ", get(10) = " + get(h, 10));
        System.out.println("E3. count(9) = " + count(h, 9));
        System.out.println("E4. reverse = " + str(reverse(fromArray(1, 2, 3, 4, 5))));
        System.out.println("E5. removeAll(9) = " + str(removeAll(fromArray(9, 4, 9, 9, 2, 9), 9)));
        System.out.println("E6. middle([1..5]) = " + middle(fromArray(1, 2, 3, 4, 5)) + ", middle([1..6]) = " + middle(fromArray(1, 2, 3, 4, 5, 6)));
        Node s = null;
        for (int x : new int[] { 5, 2, 8, 1, 9, 3 }) s = insertSorted(s, x);
        System.out.println("E7. with sorted insertion: " + str(s));
    }
}