王道2-2-25

题目大意

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

先找到中间节点，q用两次next，p用一次next，等q为空，那么p就是中间节点对p后面的节点进行头插法，形成逆序，如123456，变成123465，*注意是465*然后进行断链，形成1234和65两条链最后进行和链162534

代码实现

void reorderList(ListNode* head) { ListNode* p=head,*q=head,*r,*s=head; if(!head) //head为空，则直接退出 return ; while(q->next){ //寻找中间结点 q=q->next; //p走一步 p=p->next; if(q->next) q=q->next; //q走两步 } q=p->next; //p所指结点为中间结点，q为后半段链表的首结点 p->next=nullptr; while(q){ //将链表后半段逆置 r=q->next; q->next=p->next; p->next=q; q=r; } q=p->next; //q指向后半段的第一个数据结点 p->next=nullptr; while(q){ //将链表后半段的结点插入到指定位置 r=q->next; //r指向后半段的下一个结点 q->next=s->next; //将q所指结点插入到s所指结点（head结点）之后 s->next=q; s=q->next; //s指向前半段的下一个插入点 q=r; } }