重排链表避坑思考

这道重排链表也算是一道在学习链表这个知识点的中等偏上难度的题目。这道题一眼望去有一个非常直观的思路1.利用双指针截取最后一个节点将其插入慢指针的next指针将倒数第二个指针的next置空2.慢指针往后走两个节点快指针到倒数第二个。不断遍历走就可以了就不多做解释了贴一个自己写的同思路的代码。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ // typedef struct ListNode SL; // void reorderList(struct ListNode* head) // { // SL* slowhead; // SL* fasthead; // if(head-nextNULL) // { // return; // } // // int k0; // while(fast-nextfast-next-next) // { // SL* pcurfast; // while(pcur-next-next) // //遍历找到倒数第二个节点 // { // pcurpcur-next;//pcur是倒数第二个节点 // } // fastpcur-next; // pcur-nextNULL; // fast-nextslow-next; // slow-nextfast; // slowslow-next-next; // fastfast-next; // }这个思路也是非常简单而又粗暴写的时候也是非常的自信啊。但是这个写法有一个问题在数据量大的时候处理时间也将是非常之长啊。这个重排完的链表和需要插入的节点放在一起我们的脑海里应该有一点非常抑制不住的想法嗯把要重排的截取下来再倒装一下嗯再来一手快慢指针的间隔插入诶这不手到擒来手拿把掐这道题了吗。非常的奈斯啊但是有一个问题出来了我们从哪里能知道到底有几个节点需要重排。我也是非常的困惑啊高中数学交了我们一个道理思路受限的时候我们要回去思考一下这道题的本质了嗯首尾相加0n,1(n-1),2(n-2)非常的直观昂前后总和为n依旧直观的可以得出一个答案前后两下标和为n,那我们可以利用高中数学知识得出均值为n/2那么我们可以知道了我们返回的节点位置就是中间节点当然这个是偶数的情况下如果是奇数个节点的时候我们思考一下由一组两个数据即前后和为n的时候才调换由简单的思考可得奇数时的中间节点不做调换重排结束的时候这个中间节点就是尾节点了。至此这道题我的思考路径就是如此了从一开始的暴力解法到后续的优化过程就结束。感谢各位读者老爷的观看。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode SL; SL* middleNode(SL* head) { if(headNULL) { return NULL; } //快慢指针一个走一步一个走两步 SL* slowhead; //SL* fastslow-next-next;链表就一个节点就不行不能这样初始化 SL* fasthead; //SL* retNULL; while(fast-nextfast-next-next)//均不为空 { fastfast-next-next; slowslow-next; } return slow; } SL* reverseList(SL* head) { SL* prev NULL; SL* curr head; while (curr) { SL* next curr-next; curr-next prev; prev curr; curr next; } return prev; } void reorderList(SL* head) { if(headNULL||head-nextNULL) { return; } SL* slowhead; SL* fastmiddleNode(head); SL* psfast; fastfast-next; ps-nextNULL; //中间节点已经返回 SL* newheadreverseList(fast); //反转完成开始插入 SL* pcurnewhead; while(newhead) { newheadpcur-next; pcur-nextslow-next; slow-nextpcur; slowslow-next-next; pcurnewhead; } }