T143、链表重排

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解

使用双端队列求解

   public void reorderList(ListNode head) {
        LinkedList<ListNode> queue = new LinkedList<>();
        ListNode temp = head;
        while(temp != null){
            queue.addLast(temp);
            temp = temp.next;
        }
        temp = head;
        while(!queue.isEmpty()){
            temp.next = queue.pollFirst();
            temp = temp.next;
            temp.next = queue.pollLast();
            temp = temp.next;
        }
        if(temp != null)
            temp.next = null;
    }