题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]

 示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

 提示：
 链表的长度范围为 [1, 5 * 10⁴]
 1 <= node.val <= 1000 

方法

线性表法

存入数组中后再构建链表

• 时间复杂度：O(n)，n为链表长度
• 空间复杂度：O(n)

class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> arr = new ArrayList<>();
        ListNode node = head;
        while (node!=null){
            arr.add(node);
            node = node.next;
        }
        int l = 0,r = arr.size()-1;
        while (l<r){
            arr.get(l).next = arr.get(r);
            l++;
            if(l==r){
               break;
            }
            arr.get(r).next = arr.get(l);
            r--;
        }
        arr.get(l).next = null;
    }
}

反转链表法

反转后半段链表然后再合并

• 时间复杂度：O(n)，n为链表长度
• 空间复杂度：O(1)

class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> arr = new ArrayList<>();
        ListNode slow = head,fast = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode node1 = head;
        ListNode node2 = reverse(slow);
        ListNode next = null;
        while (node1!=null||node2!=null){
            if(node1!=null){
                next = node1.next;
                node1.next = node2;
                node1 = next;
            }
            if(node2!=null){
                next = node2.next;
                node2.next = node1;
                node2 = next;
            }
        }
    }
    private ListNode reverse(ListNode head){
        ListNode pre = null,cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}