题解 | #重排链表#

import java.util.*;
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null) return;

        List<ListNode> list = new ArrayList<>();
        ListNode p = head, q = head.next;
        //1.将所有链表节点放入list中
        while(p != null){
            list.add(p);
            p.next = null;
            p = q;
            if(q != null)
                q = p.next;
        }
        //2.左右双指针，交错往中间靠近然后成链
        int l = 0, r = list.size()-1;
        while(l < r){
            if(l < r) list.get(l ++).next = list.get(r);
            if(l < r) list.get(r --).next = list.get(l);
        }
    }
}