题解 | #重排链表#

/**
 * 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;
    }
}