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

    // --- 带哨兵的链表（简化版）---
    static class Node {
        int value;
        Node next, prev;
        Node(int v) { value = v; }
    }

    static Node head, end;

    static void initSentinel(int... values) {
        end = new Node(0);
        head = end;
        for (int v : values) insertBefore(end, v);
    }

    static void insertBefore(Node p, int x) {
        Node q = new Node(p.value);
        q.next = p.next;
        p.value = x;
        p.next = q;
        if (p == end) end = q;
    }

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

    // E1. 带哨兵链表中最大的元素
    static int max() {
        int m = Integer.MIN_VALUE;
        for (Node p = head; p != end; p = p.next) m = Math.max(m, p.value);
        return m;
    }

    // E2. 哨兵查找 + 计数：x 出现了多少次？（多亏了哨兵，循环中只有一个条件）
    static int countSentinel(int x) {
        end.value = x;
        int c = 0;
        Node p = head;
        while (true) {
            while (p.value != x) p = p.next;
            if (p == end) return c;
            c++;
            p = p.next;
        }
    }

    // E3. 用“复制后继结点”的技巧删除所有偶数
    static void removeEven() {
        Node p = head;
        while (p != end) {
            if (p.value % 2 == 0) {
                Node q = p.next;
                p.value = q.value;
                p.next = q.next;
                if (q == end) end = p;  // p 成为新的哨兵 – 循环条件使循环结束
            } else {
                p = p.next;
            }
        }
    }

    // E4. 双向链表是否是回文？（两个指针从两端检查）
    static boolean isPalindromeDoubly(int... a) {
        Node h = null, t = null;
        for (int v : a) {
            Node n = new Node(v);
            n.prev = t;
            if (t != null) t.next = n;
            else h = n;
            t = n;
        }
        while (h != t && t.next != h) {
            if (h.value != t.value) return false;
            h = h.next;
            t = t.prev;
        }
        return true;
    }

    // E5. 循环链表的结点个数（do-while）
    static int circularSize(Node last) {
        if (last == null) return 0;
        int c = 0;
        Node p = last.next;
        do {
            c++;
            p = p.next;
        } while (p != last.next);
        return c;
    }

    public static void main(String[] args) {
        initSentinel(4, 9, 2, 9, 7, 6);
        System.out.println("E1. list " + sentinelStr() + ", max = " + max());
        System.out.println("E2. countSentinel(9) = " + countSentinel(9) + ", countSentinel(5) = " + countSentinel(5));
        removeEven();
        System.out.println("E3. after deleting the even elements: " + sentinelStr());
        System.out.println("E4. is [1,2,3,2,1] a palindrome? " + isPalindromeDoubly(1, 2, 3, 2, 1) + ", [1,2,2,3]? " + isPalindromeDoubly(1, 2, 2, 3));
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b;
        b.next = c;
        c.next = a; // 环：last = c
        System.out.println("E5. size of the circular list: " + circularSize(c));
    }
}