題目

• 給定一個(gè)單鏈表從L0->L1->...->Ln-1->Ln將其重新排列為L(zhǎng)0->Ln->L1->Ln-1->L2->Ln-2->...
• 舉例:輸入1->2->3->4, 重排為 1->4->2->3.

解法一（采用壓棧的方式）

• 首先這個(gè)鏈表肯定是分段為兩部分，從中間斷開(kāi)，而后面的是按照逆序插入到前半部分中的，如果是直接遍歷索引我們是無(wú)法做逆序插入的，鏈表只能從前往后索引不能從后往前
• 就可以采用入棧的方式，將所有的鏈表壓入棧，此時(shí)棧頂元素就是鏈表最后一個(gè)節(jié)點(diǎn)，依次就可以取得第n n-1 n-2個(gè)數(shù)
• 然后我們從head.next開(kāi)始遍歷，從head節(jié)點(diǎn)開(kāi)始插入，每次從棧中取出一個(gè)元素插入到head鏈表中，然后再?gòu)膆ead.next的前鏈表中取出一個(gè)元素插入，完成整個(gè)鏈表的重排

棧的代碼實(shí)現(xiàn)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        Stack<ListNode> stack = new Stack<>();
        ListNode index = head.next;
        while (index != null) {
            stack.push(index);
            index = index.next;
        }
        index = head.next;
        ListNode p = head;
        int count = 0;
        while (count < stack.size()) {
        //每一次count+1, stack-1整體變化為2
            p.next = stack.pop();
            p = p.next;
            p.next = index;
            index = index.next;
            p = p.next;
            count++;
        }
        p.next = null;
    }
}

解法二（快慢雙指針）

• 解法三部曲
• slow和fast分別從head開(kāi)始遍歷，slow每次移動(dòng)一個(gè)next,fast移動(dòng)兩個(gè)next，當(dāng)fast到達(dá)null結(jié)束循環(huán)時(shí)，此時(shí)slow就是我們需要的第一個(gè)分段的最后一個(gè)數(shù)據(jù)。
• 將此時(shí)slow之后的片段2進(jìn)行逆序重排比如1->2->3->4重排為1->2->4->3，因?yàn)榇藭r(shí)slow是指向2的。
• 第三步，把數(shù)據(jù)按照前后交叉整合，即可得到最后的結(jié)果1->4->2->3
• 空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(n)

代碼二

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode slow = head, fast = head;
        //找到前半部分鏈表
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //后半段頭插法改變鏈表順序
        ListNode index = slow.next;
        slow.next = null;
        while (index != null) {
            ListNode temp = index;
            index = index.next;
            temp.next = slow.next;
            slow.next = temp;
        }
        //前后交叉合并為一個(gè)鏈表
        ListNode pre = head;
        index = slow.next;
        while (pre != slow) {
            slow.next = index.next;
            index.next = pre.next;
            pre.next = index;
            pre = index.next;
            index = slow.next;
        }
    }
}

參考鏈接

https://www.cnblogs.com/woainifanfan/p/6511943.html