/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The head of linked list. * @return: void */ public void reorderList(ListNode head) { // write your code here if(head==null){ return; } int count=1; ListNode node1=head; while(node1.next!=null){ node1=node1.next; count++; } ListNode node=head; ListNode result=head; Queue<ListNode> q=new LinkedList<ListNode>(); Stack<ListNode> s=new Stack<ListNode>(); if(count%2==0){ int num=count/2; while(num>0){ ListNode temp=node.next; node.next=null; q.add(node); node=temp; num--; } while(node!=null){ ListNode temp=node.next; node.next=null; s.push(node); node=temp; } q.poll(); while(!s.isEmpty()){ ListNode temp=s.pop(); result.next=temp; result=result.next; if(!q.isEmpty()){ temp=q.poll(); result.next=temp; result=result.next; }else{ break; } } }else{ int num=count/2+1; while(num>0){ ListNode temp=node.next; node.next=null; q.add(node); node=temp; num--; } while(node!=null){ ListNode temp=node.next; node.next=null; s.push(node); node=temp; } q.poll(); while(!s.isEmpty()){ ListNode temp=s.pop(); result.next=temp; result=result.next; if(!q.isEmpty()){ temp=q.poll(); result.next=temp; result=result.next; } } } } }
