【C++】链表操作技巧综合：重排链表（带你理顺链表的做题思路）

1.题目

2.算法思路

这是一道关于链表的综合题，一共涉及到三个步骤，其中每个步骤单拎出来就可以当一道单独的题目。所以需要大家对链表的操作十分熟悉，否则可能需要大量的时间做这道题目，而且还要很多的bug。

第一个步骤：

找到链表的中间结点。

技巧：快慢双指针。快指针往后走两步，慢指针往后走一步，当快指针走到链表的结尾时，慢指针刚好落在链表的中间位置。

注意：当链表有偶数个结点时，想要改变慢指针最后的落点，可以在链表前面插入一个哨兵位的头结点。

第二个步骤：

翻转后半部分的链表。

这里依然需要一个哨兵位的头结点，这样可以大大降低代码的复杂程度，也可以排除边界情况。总之，做链表的题目离不开哨兵位的头结点，能用就用。

然后往这个哨兵位的头结点后边一直头插就可以实现链表的翻转。

第三个步骤：

两个链表的合并。

这里需要双指针和哨兵位的头结点，分别遍历两个链表，然后分别在哨兵位的头结点后尾插即可完成题目！

3.思路总结

不只是针对这一道题目，而是针对所有的链表题目：

1.尽量多运用哨兵位的头结点。

2.尽量避免在原链表上做修改，这样代码会显得很乱。尽可能在哨兵位的头结点后进行尾插或头插，这样更有条理。

4.代码

void reorderList(ListNode* head) {if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;//快慢双指针，寻找中间结点ListNode* newhead=new ListNode(0,head);ListNode* slow=newhead,*fast=newhead;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//从中间位置断开链表ListNode* cur=slow->next;slow->next=nullptr;//利用头插法翻转后半部分的链表ListNode* ret=new ListNode(0);ListNode* prev=ret;while(cur){ListNode* next=cur->next;cur->next=prev->next;prev->next=cur;cur=next;}//合并两个链表（双指针）ListNode* head1=new ListNode(0);ListNode* cur1=head,*cur2=ret->next,*prev1=head1;while(cur1){if(cur1){prev1->next=cur1;prev1=cur1;cur1=cur1->next;}if(cur2){prev1->next=cur2;prev1=cur2;cur2=cur2->next;}}//释放哨兵位的头结点，防止内存泄漏。delete newhead;delete ret;delete head1;}