题解 | #重排链表#

要求真高

1. 这种重排需求应该没有意义，但是它还要求原节点操作，于是就有些细节了。
2. 神奇的点：无论是偶数节点还是奇数节点，都是while内部break。

具体代码：

//    L0-> Ln-> L1-> L n1-> L2-> L n2-> …
    public void reorderList(ListNode head) {
        // 边界判断
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode slowPre = null;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slowPre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        slowPre.next = null; //断掉
//      ListNode mid = slow;  这个时候，slow就是mid节点，而且从mid之后就算是后一半链表。
        ListNode lastHalf = new ListNode(0);
        while (slow != null) {
            // 把后一半链表进行翻转——头插法
            ListNode p = slow;
            slow = slow.next;
            // 摘下p节点
            p.next = lastHalf.next;
            lastHalf.next = p;
        }
        ListNode p = head;
        ListNode pp = lastHalf.next;
        while (true) {
            ListNode oneP = pp; //摘下oneP
            pp = pp.next;
            oneP.next = p.next;
            p.next = oneP;
            p = p.next;
            if (p.next == null) { // 无论是偶数节点还是奇数节点，都是在这里break。神奇不？
                p.next = pp;
                break;
            } else {
                p = p.next;
            }
        }

        /* 1 2 3 4 5
         *   s f
         *     s   f
         *
         *
         *
         * 1 2 3 4
         *   s f
         *     s   f
         *
         * 1 2 3
         *   s f
         * */
    }