143. 重排链表

题目:https://leetcode-cn.com/problems/reorder-list/

代码:

class Solution {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        //链表转成list存储
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        //重排
        int size = list.size();
        for (int i = 0; i < size / 2; i++) {
            ListNode node1 = list.get(i);
            ListNode node2 = list.get(size - 1 - i);
            node2.next = node1.next;
            node1.next = node2;
        }
        //处理尾部,防止循环指针
        list.get(size / 2).next = null;
    }

}

因为题目需要重排链表,且排列规则跟下标有关,而链表是没有下标属性的。为了解决这个问题,我们可以将链表转化成list,之后根据题目要求重排即可。

注意:需要处理结尾节点的next值为null,否则会造成循环指针。