题目描述

将给定的单链表L： L_0→L_1→…→L_{n-1}→L_n
重新排序为：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
示例1
输入：{1,2,3,4}
返回值：{1,4,2,3}
说明：给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出

题目分析

题目排序的意思可以理解为：将链表的尾部结点插入到链表中的头部结点之间，直到头部结点与尾部结点重合（奇数结点链表）或者之间没有其他结点（偶数结点链表）。
将链表分为（0~ n/2）头部结点部分和（n/2 ~ n-1）尾部结点部分，可以进行如图的交换。
图片说明

解题思路

方法1：使用列表数组存储结点，按下标访问交换
通过列表数组存储结点，可以使用O(1)的时间访问任意结点，避免链表每次需要从头结点遍历访问。
可以使用双指针的方式，一个指针left指向链表头部，一个指针right指向链表尾部，修改这两个结点的next指向，left和right指针分别向中间移动。

方法2：使用栈存储结点，按弹出顺序交换
利用栈的“先进后出”的特点，用栈存储结点，可以直接从栈顶倒序访问链表的结点，从而根头部结点进行交换。

代码实现

方法1：使用列表数组存储结点，按下标访问交换

public void reorderList(ListNode head) {
        if(head == null) return;
        ListNode tmp = head;
        // 存储链表所有结点数据
        ArrayList<ListNode> list = new ArrayList<ListNode>();
        int n = 0;
        while(tmp != null){
            list.add(tmp);
            tmp = tmp.next;
            n++;
        }
        int left = 0;
        int right = n-1;
        while(left<right){
            // 获取头部结点
            ListNode pre = list.get(left);
            // 获取尾部结点
            ListNode end = list.get(right);
            // 指向尾部结点
            pre.next = end;
            left++;
            // 若到了中间，则交换完成退出
            if(left == right) break;
            // 指向头部下一个结点
            end.next = list.get(left);
            right--;
        }
        // 最后的尾部结点指向null
        list.get(right).next = null;
    }

时间复杂度：O(n)，n为链表长度，需要遍历链表1次时间为n，循环交换时间n/2，所以时间复杂度为O(n)；
空间复杂度：O(n)，借助了长度为n的列表来存储结点。

方法2：使用栈存储结点，按弹出顺序交换

public void reorderList(ListNode head) {
        ListNode tmp = head;
        // 存储链表所有结点数据，使用栈先处理末尾的结点
        Stack<ListNode> stack = new Stack<ListNode>();
        int n = 0;
        while(tmp != null){
            stack.push(tmp);
            tmp = tmp.next;
            n++;
        }
        tmp = head;
        // 计算需要进行交换的结点数
        int num = (n-1)/2;
        while(num>0 && tmp != null && !stack.isEmpty()){
            // 获取尾部结点
            ListNode end = stack.pop();
            ListNode next = tmp.next;
            // 将尾部节点插入到当前结点的后一个
            end.next = next;
            tmp.next = end;
            tmp = next;
            num--;
            // 将倒数前一个结点尾部置空
            stack.peek().next = null;
        }
    }

时间复杂度：O(n)，n为链表长度，需要遍历链表1次时间为n，循环交换时间n/2，所以时间复杂度为O(n)；
空间复杂度：O(n)，借助了长度为n的栈来存储结点。