---

題目鏈接：

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