深圳建设局官方网站,网站设计建站,电商网站排行,wordpress ecommerce theme1.题目 2.算法思路
这是一道关于链表的综合题#xff0c;一共涉及到三个步骤#xff0c;其中每个步骤单拎出来就可以当一道单独的题目。所以需要大家对链表的操作十分熟悉#xff0c;否则可能需要大量的时间做这道题目#xff0c;而且还要很多的bug。
第一个步骤#xf… 1.题目 2.算法思路
这是一道关于链表的综合题一共涉及到三个步骤其中每个步骤单拎出来就可以当一道单独的题目。所以需要大家对链表的操作十分熟悉否则可能需要大量的时间做这道题目而且还要很多的bug。
第一个步骤
找到链表的中间结点。
技巧快慢双指针。快指针往后走两步慢指针往后走一步当快指针走到链表的结尾时慢指针刚好落在链表的中间位置。
注意当链表有偶数个结点时想要改变慢指针最后的落点可以在链表前面插入一个哨兵位的头结点。
第二个步骤
翻转后半部分的链表。
这里依然需要一个哨兵位的头结点这样可以大大降低代码的复杂程度也可以排除边界情况。总之做链表的题目离不开哨兵位的头结点能用就用。
然后往这个哨兵位的头结点后边一直头插就可以实现链表的翻转。
第三个步骤
两个链表的合并。
这里需要双指针和哨兵位的头结点分别遍历两个链表然后分别在哨兵位的头结点后尾插即可完成题目
3.思路总结
不只是针对这一道题目而是针对所有的链表题目
1.尽量多运用哨兵位的头结点。
2.尽量避免在原链表上做修改这样代码会显得很乱。尽可能在哨兵位的头结点后进行尾插或头插这样更有条理。
4.代码 void reorderList(ListNode* head) {if(headnullptr||head-nextnullptr||head-next-nextnullptr) return;//快慢双指针寻找中间结点ListNode* newheadnew ListNode(0,head);ListNode* slownewhead,*fastnewhead;while(fastfast-next){slowslow-next;fastfast-next-next;}//从中间位置断开链表ListNode* curslow-next;slow-nextnullptr;//利用头插法翻转后半部分的链表ListNode* retnew ListNode(0);ListNode* prevret;while(cur){ListNode* nextcur-next;cur-nextprev-next;prev-nextcur;curnext;}//合并两个链表双指针ListNode* head1new ListNode(0);ListNode* cur1head,*cur2ret-next,*prev1head1;while(cur1){if(cur1){prev1-nextcur1;prev1cur1;cur1cur1-next;}if(cur2){prev1-nextcur2;prev1cur2;cur2cur2-next;}}//释放哨兵位的头结点防止内存泄漏。delete newhead;delete ret;delete head1;}
