Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

題意：重新設(shè)置鏈表順序，要求第一個(gè)節(jié)點(diǎn)連接最后一個(gè)，然后最后一個(gè)連接第二個(gè)，第二個(gè)再連接倒數(shù)第二個(gè)。。。

思路：

1. 把鏈表看做左右兩部分，先找到右半部分的起始節(jié)點(diǎn)。(奇數(shù)個(gè)時(shí)，右半部分起始是中間節(jié)點(diǎn)的next)。

2. 把右半部分節(jié)點(diǎn)入棧，這樣棧頂節(jié)點(diǎn)就是鏈表的尾巴。

3. 從鏈表頭部開(kāi)始，不斷把左半部分的節(jié)點(diǎn)和棧頂彈出的節(jié)點(diǎn)相連。

    public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
   
    //找后側(cè)的起始節(jié)點(diǎn)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode rStart = fast == null ? slow : slow.next;
   
    //記錄右側(cè)待連接的節(jié)點(diǎn)
    Stack<ListNode> stack = new Stack<>();
    while (rStart != null) {
        stack.push(rStart);
        rStart = rStart.next;
    }
   
    //連接工作
    ListNode curLeft = head;
    while (!stack.isEmpty()) {
        ListNode nextLeft = curLeft.next;
        ListNode curRight = stack.pop();
        curLeft.next = curRight;
        //如果下個(gè)待連接的左節(jié)點(diǎn)就是當(dāng)前連接的右節(jié)點(diǎn)，那么此時(shí)curLeft和curRight就是鏈表中相鄰的節(jié)點(diǎn)
        if (nextLeft == curRight) {
            nextLeft = null;
        }
        curRight.next = nextLeft;
        curLeft = nextLeft;
    }
    if (curLeft != null) {
        curLeft.next = null;
    }
    }