Leetcode_143_Reorder List

[lihe]

Reorder List

Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→L**n→L1→L**n-1→L2→L**n-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

算法思路：利用栈来找到链尾，然后从头开始遍历，重新组成链表，原链表和栈交替链接。

class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        
        while(p != null){
            stack.push(p);
            p = p.next;
        }

        if(stack.size() <= 2){
            return;
        }

        p = head;

        int size = stack.size();

        for(int i = 0; i < size / 2; i++){
            ListNode next = p.next;
            p.next = stack.pop();
            p.next.next = next;
            p = next;
        }

        p.next = null;
        return;
    }
}