题解 | #重排链表#

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null) return;
        List<ListNode> nodes = new ArrayList<>();
        ListNode cur = head;
        while(cur!=null){ // 将链表保存到list里
            nodes.add(cur);
            cur = cur.next;
        }
        cur = head;
        for (int i = 0; i < nodes.size()/2; i++) { // 组装
            ListNode right = nodes.get(nodes.size() - i - 1);
            right.next = cur.next;
            cur.next = right;
            cur = right.next;
        }
        cur.next = null;
    }
}