学步园

题目

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 首先先找到链表的中间部位。(fast--slow模块)

3 之后想到把前后两个链表分开，就是中间部位之后加null。加null的好处是，最后合并的时候，少了很多操作。

4 把后半部分倒序。（链表逆转模块)

5 把两个部分穿插地合并在一起。(merge模块)

链接大牛的 http://blog.csdn.net/fightforyourdream/article/details/17368639