链表算法综合——重排链表

此题意就是先把链表一分为二，然后把后半链表逆序并交替插入前半链表中

涉及到双指针找链表中点，头插法逆转链表的基本链表操作，具体将在代码中演示，这里我们选择不把slow指针分割成后半进行逆序而是放在前半，因为最终结果slow和前一个的位置一直不变（如果放在后也可以）

void reorderList(ListNode* head) {//以下情况不需要改变原链表if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;//找到中间节点ListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//分割链表ListNode*head2=new Listnode(0);ListNode*cur=slow->next;slow->next==nullptr;//逆序后链表while(cur){ListNode*next=cur->next;cur->next=head2->next;head2->next=cur;cur=next;}//插入ListNode*ret=new ListNode(0);ListNode*prev=ret;ListNode*cur1=head,*cur2=head2->next;while(cur1){prev->next=cur1;cur1=cur1->next;prev=prev->next;if(cur2){prev->next=cur2;cur2=cur2->next;prev=prev->next;}}delete head2;delete ret;}