重排鏈表詳解

一、鏈表與重排鏈表簡介

鏈表是一種常見的數據結構，由一系列節點組成，每個節點包含一個指針指向下一個節點。鏈表有單向鏈表、雙向鏈表、循環鏈表等多種類型，用於實現隊列、棧、圖等數據結構。重排鏈表是指給定一個鏈表，將其重排為先添加的節點排在前面，後添加的節點排在後面，而且要求原鏈表順序不變。

二、重排鏈表思路與算法

重排鏈表可以分為以下幾個步驟：

1. 使用快慢指針法，找到鏈表的中點，並將鏈表斷為兩段。

2. 將後半段翻轉，得到新的鏈表。

3. 將兩個鏈表合併，得到重排鏈表。

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
            return;
        }
        // 找到鏈表的中點
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 將鏈表斷為兩段
        ListNode* l1 = head;
        ListNode* l2 = slow->next;
        slow->next = nullptr;
        // 翻轉後半段鏈表
        ListNode* pre = nullptr;
        ListNode* cur = l2;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        l2 = pre;
        // 合併兩個鏈表
        while (l2 != nullptr) {
            ListNode* tmp1 = l1->next;
            ListNode* tmp2 = l2->next;
            l1->next = l2;
            l1 = tmp1;
            l2->next = l1;
            l2 = tmp2;
        }
    }
}; 

三、算法的時間複雜度和空間複雜度

由於需要求解中點、翻轉鏈表和合併鏈表，因此算法的時間複雜度是O(N)，其中N是鏈表的長度。由於只使用了固定數量的額外空間，因此算法的空間複雜度是O(1)。

四、重排鏈表的應用場景

重排鏈表可以用於解決鏈表相關的問題，例如鏈表的歸併排序、鏈表的交叉點等。此外，重排鏈表還可以用於實現一些要求交錯順序的場合，例如打印時需要將兩個隊列依次交錯輸出。

五、總結

重排鏈表是一種在鏈表上進行部分翻轉、合併操作的算法。其核心思想是將鏈表分成兩部分，對後半段進行翻轉，然後按照交錯的順序拼接前後兩段鏈表得到重排鏈表。該算法的時間複雜度為O(N)，空間複雜度為O(1)。重排鏈表常用於解決鏈表相關的問題，在某些場合下還能快速實現交錯順序的效果。