题解 | #重排链表#

首先理清思路，重排链表的结果就是，合并前半部分和倒着的后半部分。

由此，确定两种思路：

O(n): 使用一个列表存储链表元素，前顺序，后逆序，直至相遇

O(1): 首先选取中间位置，翻转后半部分，合并两部分链表，这实际上是三个函数的代码，一定要对每一个步骤都心里有数

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;

public class Solution {
    public void reorderList(ListNode head) {
        // O(1): 首先选取中间位置，翻转后半部分，合并两部分链表
        // O(n): 使用一个链表存储元素，逆序取
        if (head == null || head.next == null) {
            return;
        }
        /* ListNode n = head;
        ArrayList<ListNode> list = new ArrayList<>();
        while (n != null) {
            list.add(n);
            n = n.next;
        }

        // 交换
        int l = 0, r = list.size() - 1;
        while (l < r) {
            list.get(l).next = list.get(r);
            list.get(r).next = list.get(l + 1);
            l++;
            r--;
        }
        list.get(l).next = null; */
        // 获取中间位置
        ListNode middle = getMiddle(head);
        ListNode n2 = reverse(middle.next);
        ListNode n1 = head, h1 = head;
        while (n1 != null) {
            if (n1.equals(middle)) {
                n1.next = null;
            }
            n1 = n1.next;
        }
        head = rebase(h1, n2);

    }

    private ListNode rebase(ListNode n1, ListNode n2) {
        if (n1 == null || n2 == null) {
            return null;
        }
        ListNode h1 = n1, h2 = n2, next1 = h1.next, next2 = h2.next;
        while (n1 != null && n2 != null) {
            next1 = n1.next;
            next2 = n2.next;
            n1.next = n2;
            if (next1 != null) {
                n2.next = next1;
            }
            n1 = next1;
            n2 = next2;
        }
        return h1;
    }

    private ListNode getMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        System.out.println(slow.val);
        return slow;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null, node = head, next = head.next;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        System.out.println(head.val);
        return pre;
    }
}