leetcode--08. 链表重组

题目：
Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…
You must do this in-place without altering the nodes' values.
For example,
Given{1,2,3,4}, reorder it to{1,4,2,3}.
给定单链表L：L0→L 1→…→L_n-1→L_n，
将其重新排序为：l_0→L_n→L_1→L_n-1→L_2→L_n-2→…
你必须在不改变节点值的情况下就地执行此操作。
例如，给定{1，2，3，4}，将其重新排序为{1，4，2，3}

思路：
分三部分

1. 找出中点，拆分列表
2. 中点后的链表反转
3. 按要求合并链表

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null)
            return;
        // 找中点
        ListNode mid = findMiddle(head);
        // 中点后的链表反转
        ListNode rev = reverse(mid);
        // 两个链表合并
        merge(head,rev);
        
    }
    private static ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private static ListNode reverse(ListNode cur){
        ListNode pre = null;
        ListNode next = cur;
        while(next != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    private static void merge(ListNode head, ListNode rev){
        ListNode headNext = null;
        ListNode revNext = null;
        while(head != null && rev != null){
            headNext = head.next;
            revNext = rev.next;
            head.next = rev;
            rev.next = headNext;
            head = headNext;
            rev = revNext;
        }
    }
}