有没有专业做网站架构图的软件,工程建设标准化期刊,360导航网址主页,网站模板建站公司文章目录 143. 重排链表解题思路 143. 重排链表
143. 重排链表
给定一个单链表 L 的头节点 head #xff0c;单链表 L 表示为#xff1a;
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为#xff1a;
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能… 文章目录 143. 重排链表解题思路 143. 重排链表
143. 重排链表
给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
示例 1 输入head [1,2,3,4]
输出[1,4,2,3]示例 2 输入head [1,2,3,4,5]
输出[1,5,2,4,3]提示
链表的长度范围为 [1, 5 * 104]1 node.val 1000 解题思路
这道题如果我们直接重排的话那么时间复杂度比较高并且程序也比较复杂所以我们要分解问题来分析
仔细想想这道题无非就是让链表从头和从末尾开始每一个节点进行合并那不就相当于是两个链表的合并操作吗对不对并且其中一个链表就是原链表中的前半部分另一个链表是原链表中后半部分的逆序比如例子中的 1-2-3-4-5前半部分可以看作是 1-2-3这道题也可以看作是 1-2最后合并结果都是一样的后半部分则是逆序的情况5-4此时将它们逐个合并起来就是 1-5-2-4-3 了
根据上面的解析我们可以把这道题分为三步来解决
找到链表的中间节点使用快慢指针就能得到此时 slow 就是中间节点逆序中间节点的右侧链表可以使用双指针或者头插法下面再讨论合并左右两个链表
上面的操作我们都是耳熟能详啦其中要注意的无非就是第二步这里介绍 头插法的使用其实就是引入一个新的头节点 newhead将右侧链表中的节点逐个头插到 newhead 后面最后得到一个只有后半部分的逆序链表而原链表中就剩下前半部分只不过要注意一些细节下面我们来讨论一下至于双指针的做法这里就不介绍了其实相对头插法来说没那么好理解
因为链表的个数可以为奇数或者是偶数所以我们要考虑一下中间节点 slow 是否要包括在头插法和逆序的操作中所以此时我们使用头插法的时候有两种策略 将中间节点 slow 后面的链表进行逆序包括中间节点 slow 其实这种情况下无论是链表个数是奇数还是偶数的话使用头插法的时候都不太好整因为可能会出现一些 bug如下图所示 因为我们最后是要将后半部分单独拎出来作为一个逆序链表但是此时有一个问题就是 slow 前面的节点的 next 是指向 slow 的因为我们要断开左右部分的链接此时需要将其 slow 前面的节点的 next 置为空不然在后面合并遍历的时候就会死循环。但问题是这是一个单链表要找到前面的节点的话势必要重新遍历时间复杂度就提高了所以这种包括中间节点的也一起头插和逆序的操作是 不推荐 的不如使用下面的策略 将中间节点 slow 后面的链表进行逆序但 不包括中间节点 slow 此时这种情况就比较好办了无论链表的个数是奇数还是偶数此时中间节点最后都不属于右半部分的而是属于前半部分的那么同样两个链表要断开连接的话就在中间节点 slow 断开这就非常简单了直接就是一个 slow-next nullptr 就解决了非常的高效和简单 比如举个例子如下图所示
此外需要注意的细节就是在进行逆序头插法的时候需要先记录一下当前节点的下一个节点防止指向改变后丢失其它就没有什么大问题了
解决了第二步那么第三步就没问题了就是要将右侧链表的每个节点插入到左侧链表的每个节点中下面直接给出代码具体过程可以结合自己画图来分析都是不难的只是流程多而已
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {// 1. 找到链表的中间节点ListNode* fast head;ListNode* slow head;while(fast ! nullptr fast-next ! nullptr){slow slow-next;fast fast-next-next;}// 2. 逆序中间节点之后的链表但不包括中间节点此时slow就是中间节点ListNode* newhead new ListNode(0, nullptr);ListNode* right slow-next;while(right ! nullptr){ListNode* next right-next; // 先记录下一个节点防止丢失right-next newhead-next;newhead-next right;right next;}// 3. 合并左右两个链表slow-next nullptr; // 记得要断开左右链表的连接不然会死循环ListNode* cur1 head;ListNode* cur2 newhead-next;while(cur1 ! nullptr cur2 ! nullptr){ListNode* next1 cur1-next;ListNode* next2 cur2-next;cur1-next cur2;cur2-next next1;cur1 next1;cur2 next2;}delete newhead; // 别忘了要释放节点}
};
