先将链表普通入队,再一个前一个后出队,时间O(2n),空间O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null || head.next==null) return;
Deque<ListNode> dq=new LinkedList();
ListNode cur=head;
int count=0;
while(cur!=null){
count++;
ListNode next=cur.next;
cur.next=null;
dq.addLast(cur);
cur=next;
}
ListNode dummy=new ListNode(123);
cur=dummy;
for(int i=0;i<count;i++){
if((i&1)==0){
cur.next=dq.removeFirst();
}else{
cur.next=dq.removeLast();
}
cur=cur.next;
}
}
}