题目

• 给定一个单链表从L0->L1->...->Ln-1->Ln将其重新排列为L0->Ln->L1->Ln-1->L2->Ln-2->...
• 举例:输入1->2->3->4, 重排为 1->4->2->3.

解法一（采用压栈的方式）

• 首先这个链表肯定是分段为两部分，从中间断开，而后面的是按照逆序插入到前半部分中的，如果是直接遍历索引我们是无法做逆序插入的，链表只能从前往后索引不能从后往前
• 就可以采用入栈的方式，将所有的链表压入栈，此时栈顶元素就是链表最后一个节点，依次就可以取得第n n-1 n-2个数
• 然后我们从head.next开始遍历，从head节点开始插入，每次从栈中取出一个元素插入到head链表中，然后再从head.next的前链表中取出一个元素插入，完成整个链表的重排

栈的代码实现

/**
 * 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开始遍历，slow每次移动一个next,fast移动两个next，当fast到达null结束循环时，此时slow就是我们需要的第一个分段的最后一个数据。
• 将此时slow之后的片段2进行逆序重排比如1->2->3->4重排为1->2->4->3，因为此时slow是指向2的。
• 第三步，把数据按照前后交叉整合，即可得到最后的结果1->4->2->3
• 空间复杂度O(1)，时间复杂度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;
        }
        //前后交叉合并为一个链表
        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