这道题参考了Discuss 中一个前辈的思路：把输入的链表分成前后两半，将后半链表reverse，最后merge成目标链表。
1 /** 2 * reorder the list in-place without altering the nodes' value 3 * 参考了讨论中前辈提供的一种思路O(N)时间复杂度、O(1)空间复杂度 4 * @param head 5 */ 6 public void reorderList(ListNode head){ 7 if(head == null || head.next == null) 8 return ; 9 int len = 0; 10 ListNode curr = head,temp = null; 11 //caculate the length of the list 12 while(curr!=null) 13 { 14 len ++ ; 15 curr = curr.next; 16 } 17 18 int i = 0; 19 temp = null; // after the while, temp is the end of the first half List; 20 curr = head;// after the while, curr is the head of the second half List 21 while(i++<(len-len/2)) 22 { 23 temp = curr; 24 curr = curr.next; 25 } 26 temp.next = null;// the next of the new end should be null 27 28 //reverse the second half List 29 ListNode shead = curr; 30 ListNode po = curr.next; 31 shead.next = null; 32 while(po!=null) 33 { 34 ListNode t = po.next; 35 po.next = shead; 36 shead = po; 37 po = t; 38 } 39 40 //merge the first half and the second reversed half 41 po = head; 42 while(shead !=null){ 43 ListNode f1 = po.next; 44 ListNode f2 = shead.next; 45 po.next = shead; 46 shead.next = f1; 47 po = f1; 48 shead = f2; 49 } 50 }