如果做了回文链表这道题,会惊奇地发现两题的解决思路如此相似:找到链表的中点,反转后半段链表,把反转后的链表的结点一个一个地插入原链表的中间。

有思想,做起来就很快,但是要注意的是,使用哪种方式反转?
下面这段代码的反转方式就没有断掉原链表中间的结点与要反转的链表段的连接,当遍历到最后的时候,会发现最后两个结点成环……

class Solution {
    public void reorderList(ListNode head) {
        // 特殊判断
        if(head == null){
            return ;
        }
        ListNode cur = head, pre = head;
        // 利用快慢指针,找到后半段链表的头结点,pre指向它
        while(cur != null && cur.next != null){
            cur = cur.next.next;
            pre = pre.next;
        }
        // 反转后半段链表
        // 注意,这里会有环!pre指向的是要反转的链表的头一个,但是这里并没有解开pre的前一个结点的next依然指向pre,
        ListNode newHead = null;
        while(pre != null){
            ListNode nextNode = pre.next;
            pre.next = newHead;
            newHead = pre;
            pre = nextNode;
        }
        // 把反转后的链表插入原链表中
        while(newHead != null){
            ListNode nextNode = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = nextNode;
        }
        // 上面反转造成的环,是前半段的最后一个结点与newHead的最后一个结点成环
        head.next = null;
    }
}