定西市建设局官方网站,编程入门教学,wordpress单页留言聊天,h5企业模板网站模板文章目录 题目链接#xff1a;题目描述#xff1a;解法C 算法代码#xff1a; 题目链接#xff1a;
143. 重排链表 题目描述#xff1a; 解法 模拟 找到链表的中间节点 快慢双指针 把后面的部分逆序 双指针#xff0c;三指针#xff0c;头插法 合并两个链表 合并两个有… 文章目录 题目链接题目描述解法C 算法代码 题目链接
143. 重排链表 题目描述 解法 模拟 找到链表的中间节点 快慢双指针 把后面的部分逆序 双指针三指针头插法 合并两个链表 合并两个有序链表双指针 C 算法代码
/*** 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) {// 处理边界情况// 如果链表为空、只有一个节点或只有两个节点无需重排if(head nullptr || head-next nullptr || head-next-next nullptr) return;// 1. 找到链表的中间节点 - 使用快慢双指针法// slow最终会指向中间节点对于奇数长度链表指向正中间对于偶数长度链表指向中间靠左的节点ListNode* slow head, *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}// 2. 将链表的后半部分逆序 - 使用头插法ListNode* head2 new ListNode(0); // 创建虚拟头节点用于后半部分逆序ListNode* cur slow-next;slow-next nullptr; // 断开链表前半部分以slow为尾节点// 遍历后半部分并进行逆序while(cur){ListNode* next cur-next; // 保存下一个节点cur-next head2-next; // 当前节点指向头节点的下一个head2-next cur; // 头节点指向当前节点实现头插cur next; // 移动到下一个节点}// 3. 合并两个链表 - 一个节点来自第一个链表一个节点来自第二个链表ListNode* ret new ListNode(0); // 创建虚拟头节点用于合并结果ListNode* prev ret;ListNode* cur1 head; // 前半部分链表的头节点ListNode* cur2 head2-next; // 后半部分逆序后的头节点// 交替合并两个链表while(cur1){// 先放入前半部分的节点prev-next cur1;cur1 cur1-next;prev prev-next;// 再放入后半部分的节点如果有if(cur2){prev-next cur2;prev prev-next;cur2 cur2-next;}}// 释放临时创建的虚拟头节点delete head2;delete ret;}
};
