1、前言

2、思路

使用栈存储。

3、代码

class Solution {
    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode p = head, q = null;
        while(p != null){
            stack.push(p);
            p = p.next;
        }

        p = head;
        while(p != null && p.next != p && !stack.isEmpty()){
            q = stack.pop();
            q.next = null;
            ListNode nextNode = p.next;
            q.next = nextNode;
            p.next = q;

            p = nextNode;
        }

        if(q != null){
            q.next = null;
        }
    }
}