Reorder List

Given a singly linked list L: L₀ → L₁ → … → L_n-1 → L_n
reorder it to: L₀ → L_n → L₁ → L_n-1 → L₂ → L_n-2 → …

Example

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

My solution is better than popular solution on web, which separate list into two halves, then reverse right list and then merge the two list. I use stack at first place. They are similar approaches, mine has less code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

/** * 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 //everytime a list need to be reversed, think about stask if(head==null)return ; Stack<ListNode> stack = new Stack<ListNode>(); ListNode p=head; int len=0; while(p!=null){ stack.push(p); p=p.next; len++; } if(len<=2)return; p=head; int cnt=1;//this is important.try to demo it one paper to choose right value ListNode rear=stack.pop(); while(cnt<(len+1)/2){ ListNode tmp = p.next;//original next node p.next=rear; rear.next=tmp; p=tmp;//move p to original next node if(!stack.isEmpty()) rear=stack.pop(); cnt++; } rear.next=null;//also p has pointed to rear in the loop. it is rear, that needs to be closed return ; } }