143. 重排链表：先快慢指针二分链表，再反转右链表，最后将右链表插入左链表.md

题目简述：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题目链接：143. 重排链表

思路

1. 首先利用快慢指针二分链表（慢指针自增 1、快指针自增 2，利用哨兵节点方便初始化），找到右链表的起始节点，方便在第二步反转右链表，同时将左链表的尾元素 next 字段设为 null，分离左右链表；
2. 反转右链表，得到反转后右链表的起始节点，方便在第三步将右链表元素逐个插入左链表；
3. 将右链表逐个插入左链表中。由于第一步在二分原链表时保证了右链表的长度一定是左链表的长度或左链表的长度减 1，因此在一个循环中进行逐个插入即可，循环终止条件为右链表被全部插入。

编写代码的注意点和设计原理都已经在代码注释中说明了。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */


class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return;

        // 1. 利用快慢指针二分链表
        int len = 0;
        // midNode 是右半部分链表起始的首个节点
        ListNode midNode = head, tailNode = head;
        // 使用哨兵节点初始化 midNode 的上一节点以便断开左半部分链表与右半部分链表的连接
        ListNode midLastNode = new ListNode(0, midNode);
        while (tailNode != null && tailNode.next != null) {
            midNode = midNode.next;
            midLastNode = midLastNode.next;
            tailNode = tailNode.next.next;
            len++;
        }
        // 单独处理奇数个节点的情形
        if (tailNode != null) {
            midNode = midNode.next;
            midLastNode.next.next = null;
        } else {
            midLastNode.next = null;
        }


        // 2. 反转右半部分链表
        ListNode reversedHead = reverse(midNode);

        // 3. 将反转后的右半部分链表逐个插入左半部分中
        ListNode leftNode = head;
        ListNode rightNode = reversedHead;
        while (rightNode != null) {
            ListNode tempLeftNode = leftNode.next;    // assume 0(leftNode) -> 1, insert 2(rightNode) -> 3, let tempLeftNode = 1
            ListNode tempRightNode = rightNode.next;  // let tempRightNode = 3
            leftNode.next = rightNode;                // 0(leftNode) -> 1(rightNode)
            rightNode.next = tempLeftNode;            // 1 -> 2(tempLeftNode)
            leftNode = tempLeftNode;                  // 0 -> 1 -> 2(leftNode), 3
            rightNode = tempRightNode;                // 0 -> 1 -> 2(leftNode), 3(rightNode)
        }
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode thisNode = head.next;
        ListNode lastNode = head;

        while (thisNode.next != null) {
            ListNode tempNode = thisNode.next;
            thisNode.next = lastNode;
            lastNode = thisNode;
            thisNode = tempNode;
        }
        thisNode.next = lastNode;
        head.next = null;
        return thisNode;
    }
}