ReOrderList
再次遇到又爱又恨的linklist，这是必须卖过的坎，好像某软喜欢考Linklist相关的，包括CopyRandomLinklist，两个Linklist第一个交点等等。
这道是13年MS笔试的最后一题，几个月前做的时候，是纸上写，好像不是太难，1 2 3 4 -> 1 4 2 3, 也即两项index和相同这样一个一个pair排列，立马要想到处理奇偶个结点的情况。
可以这么思考，index 从 1 2 3 4 map到 1 4 2 3, 将后面逆置，然后逐个插入到前面的linklist，思路不难，但是Linklist一定要写好，还是要把诸多情况考虑清楚的。
- 遍历求长度 n
- 找到后半的第一个结点 n/2
- 后半reverse， n/2
- 后半插入到前半中 n/2
第二步要考虑奇偶性，如果奇数需要多移动一个点，后半reverse使用三个指针，注意不丢next指针，插入也是这样。
附上代码：
void reorderList(ListNode *head)
{
if(head==NULL || head->next==NULL || head->next->next==NULL) return ;
ListNode* p=head;
int l=0;
while(p) p=p->next,l++;//imitate adhoc's code style
p=head;
int i=0;
ListNode* prev;
while(i<l/2) prev=p,p=p->next ,i++;//imitate adhoc's code style
if(l%2==1) prev=p,p=p->next;//odd, p to be (l-1)/2+1 node, prev to be center
ListNode* pnext, *pprev=NULL;
while(p!=NULL)//reverse, pprev, p,pnext
{
pnext=p->next;
p->next=pprev;
pprev=p;
p=pnext;
}
prev->next=NULL;//center link to reversed list node, avoid first part last node point to second part first node, which lead to loop linklist
//pprev;
p=head;ListNode* q=pprev, *qnext;
while(q!=NULL&&p!=NULL)
{
pnext=p->next;//record p original next
qnext=q->next;
p->next=q;
q->next=pnext;
p=pnext;
q=qnext;
}
}
还好这次没有调试太久，遇到的问题有：
- Showlist测试忘记pnext导致死循环= =
- 代码敲错的问题，while里面三句逗号连接，模仿一博，结果i++前面敲成; 号了o(╯□╰)o reverse最后一个p=pnext 敲成p=p->next 这种问题最2了，浪费很多时间
- 最关键的一个bug，后面reverse之后，我之前是把他和前面链接成一个链表了，千万不要，因为后面p q往后指的时候，最后一次loop p链最后一个指到q第一个了，于是链表循环了，除非里面加逻辑特殊处理，简洁的
办法就是两个链表断开，不要链接，因为后面链接的头结束reverse后是知道的(pprev)，不会丢失，只要不丢point就行了。