【C++算法】53.链表_重排链表

---

题目链接：

143. 重排链表

---

题目描述：

---

解法

模拟

1. 找到链表的中间节点
   1. 快慢双指针
2. 把后面的部分逆序
   1. 双指针，三指针，头插法
3. 合并两个链表
   1. 合并两个有序链表（双指针）

---

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;}
};