题解 | #重排链表#

时间复杂度O(n),额外空间复杂度O(n)

import java.util.*;
public class Solution {
    private Map<Integer, ListNode> map = new HashMap<>();
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        int size = storeIntoMap(head);
        for (int i = 0,j=size-1;i <= j; i++,j--) {
            ListNode top = map.get(i);
            ListNode tail = map.get(j);
            if (i == j) {
                top.next = null;
                break;
            }
            if (tail != top.next) {
                tail.next = top.next;
            } else {
                tail.next = null;
            }
            top.next = tail;



        }

    }

    public int storeIntoMap(ListNode node) {
        int i = 0;
        while(node != null) {
            map.put(i++, node);
            node = node.next;
        }
        return i;
    }

}

借助map记录每个索引位置上的节点，然后重组链表即可，需要考虑数据的奇偶个数和最后一个节点的next指针处理。