Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You must do this in-place without altering the nodes' values.For example,Given {
    1,2,3,4}, reorder it to {1,4,2,3}.

这是一道比较综合的链表操作的题目，要按照题目要求给链表重新连接成要求的结果。其实理清思路也比较简单，分三步完成：（1）将链表切成两半，也就是找到中点，然后截成两条链表；（2）将后面一条链表进行reverse操作，就是反转过来；（3）将两条链表按顺序依次merge起来。

这几个操作都是我们曾经接触过的操作了，第一步找中点就是用runner technique方法，一个两倍速跑，一个一倍速跑，知道快的碰到链表尾部，慢的就正好停在中点了。第二步是比较常见的reverse操作，在也有用到了，一般就是一个个的翻转过来即可。第三步是一个merge操作，做法类似于Sort List中的merge

接下来看看时间复杂度，第一步扫描链表一遍，是O(n)，第二步对半条链表做一次反转，也是O(n)，第三部对两条半链表进行合并，也是一遍O(n)。所以总的时间复杂度还是O(n)，由于过程中没有用到额外空间，所以空间复杂度O(1)。

第三遍代码（reverse LinkedList用的是最终默认方法）(实测328ms, 比其它方法快)

1 public class Solution { 2     public void reorderList(ListNode head) { 3         if (head == null) return; 4         ListNode dummy = new ListNode(-1); 5         dummy.next = head; 6         ListNode runner = dummy; 7         ListNode walker = dummy; 8         while (runner != null && runner.next != null) { 9             runner = runner.next.next;10             walker = walker.next;11         }12         ListNode head2 = walker.next;13         walker.next = null;14         head2 = reverse(head2);15         runner = head2;16         walker = head;17         ListNode prev = dummy;18         while (runner!=null && walker!=null) {19             ListNode next = runner.next;20             runner.next = walker.next;21             walker.next = runner;22             runner = next;23             walker = walker.next.next;24             prev = prev.next.next;25         }26         if (runner != null) {27             prev.next = runner;28         }29     }30     31     public ListNode reverse(ListNode header) {32         if (header == null) return null;33         ListNode dummy = new ListNode(-1);34         dummy.next = header;35         ListNode cur = header;36         while (cur.next != null) {  //find the last non-null element of this list37             cur = cur.next;38         }39         ListNode last = cur; // name the last non-null element as last40         while (dummy.next != last) {41             cur = dummy.next;42             ListNode next = cur.next;43             cur.next = last.next;44             last.next = cur;45             dummy.next = next;46         }47         return dummy.next;48     }49 }

第一遍的时候的代码：

1 /** 2  * Definition for singly-linked list. 3  * class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public void reorderList(ListNode head) {14         if (head == null || head.next == null) return;15         ListNode dummy = new ListNode(-1);16         dummy.next = head;17         ListNode current = dummy;18         ListNode runner = dummy;19         while (runner.next != null && runner.next.next != null) {20             current = current.next;21             runner = runner.next.next;22         }23         ListNode half = current.next;24         current.next = null;25         26         /*reverse the second Linked List*/27         if (runner.next != null) runner = runner.next; //make sure the runner pointer points to the end of the the second Linked List28         ListNode dummy2 = new ListNode(-2);29         dummy2.next = half;//create another dummy node whose next points to the head of the second Linked List30         while (dummy2.next != runner) {31             ListNode dnext = dummy2.next.next;32             ListNode rnext = runner.next;33             dummy2.next.next = rnext;34             runner.next = dummy2.next;35             dummy2.next = dnext;36         }37         38         /*merge the two Linked List together*/39         ListNode header1 = dummy;40         ListNode header2 = dummy2;41         while (header1.next != null && header2.next != null) {42             ListNode store = header1.next.next;43             ListNode merge = new ListNode(header2.next.val);44             header1.next.next = merge;45             merge.next = store;46             header1 = header1.next.next;47             header2 = header2.next;48         }49         if (header2.next != null) {50             header1.next = header2.next;51         }52     }53 }

 其他一些备用的reverse一个LinkedList的方法: 这些方法都很巧，但是不太好想，不太好写，我还是用默认方法吧

1 private ListNode reverse(ListNode head) 2 { 3     ListNode pre = null; 4     ListNode cur = head; 5     while(cur!=null) 6     { 7         ListNode next = cur.next; 8         cur.next = pre; 9         pre = cur;10         cur = next;11     }12     return pre;13 }     

 备用方法2：

31     public ListNode reverse(ListNode header) {32         if (header==null) return null;33         ListNode prev = new ListNode(-1);34         prev.next = header;35         ListNode cur = prev;36         ListNode node1 = header;37         ListNode node2 = header.next;38         ListNode end = header;39         while (node2 != null) {40             ListNode next = node2.next;41             cur.next = node2;42             node2.next = node1;43             node1 = node2;44             node2 = next;45         }46         end.next = null;47         return prev.next;48     }