题解 | #重排链表#

本题主要的思路是：将原链表从中间断开分为两个链表，反转后半个链表，然后依次拼接，主要涉及的两个新方法是求链表的中点和反转链表，使用快慢指针，慢走一步，快走2步。

 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    private ListNode getMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //快慢指针
        ListNode slow = head, quick = head;
        //快2步，慢一步
        while (quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        return slow;
    }

    /**
     * 重排链表
     * 将链表从中间断开分为两个链表，反转后半个链表，然后依次拼接
     *
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        //获取中间结点
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        // 这一步很关键，将链表断开，防止死循环
        mid.next = null;
        //反转后一段
        ListNode reverseNode = ReverseList(right);
        //合并前一段和后一段
        count(head, reverseNode);
    }

    public ListNode count(ListNode node1, ListNode node2) {
        ListNode numpy = new ListNode(-1);
        ListNode copyNumpy = numpy;
        int sum = 1;
        while (node1 != null && node2 != null) {
            if (sum % 2 != 0) {
                copyNumpy.next = node1;
                node1 = node1.next;
            } else {
                copyNumpy.next = node2;
                node2 = node2.next;
            }
            copyNumpy = copyNumpy.next;
            sum++;
        }
        copyNumpy.next = (node1 == null ? node2 : node1);
        return numpy.next;
    }

    //反转链表
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}