Reorder List
【题目】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. In-place 一开始的一点想法是去reverse linkedlist 然后用两个list 交叉着组合， 但是in place直接打消了所有念头。
这个时候 如果是真正面试 没有任何hint的话 一般就会陷入无比绝望中。
不过做题的时候永远就是得思考自己的goal是什么，怎么达成 T^T.
Goal: 我们需要前半部分的node指向后半部分的node somehow. 怎么做到？暂时不知道。 这时候需要想怎么样可以让后半部分的node一个一个pop out 就像前半部分的list一样。 这时候就得靠intuition 想到stack的原理了， 也就是first in last out.
That being said, 我们可以先把整个list的所有node 灌入stack里面。从前往后process，前头每pop出一个node，后面就pop出一个node。
cur = head;
while (cur!=null)
{
...........
}
