牛客經典連結清單題—(NC2)重排連結清單

合并有序連結清單

• 1. 題目描述
• 2. 題目連結
• 3. 題目剖析
• • 3.1剖析圖示
  • 3.2 圖示詳解
• 4. 解題代碼
• 5. 代碼注釋詳解

滿難度系數

* * * * *

，此題難度系數

* * *

。

滿考頻熱度

* * * * *

，此題熱度

* * * * *

。

1. 題目描述

2. 題目連結

1. 牛客題目連結重排連結清單

3. 題目剖析

1. 重排連結清單方式是從兩頭到中間交錯重排，假如連結清單有4個結點，

   重排方式是1->4->2->3

   。
2. 主要考察對連結清單的基本操作，要處處小心，

   以免越界

   考的知識點有：

   快慢指針找中間結點

   ，

   反轉連結清單

   ，

   連結清單連結

   等知識點。
3. 快慢指針找中間結點和反轉連結清單在之前題解有過詳解：反轉連結清單link
4. 具體操作如下圖解，詳細過程如下。

3.1剖析圖示

3.2 圖示詳解

1. 第一步，先利用快慢指針的思想找到中間結點。并将中間結點作為一個新連結清單的頭進行記錄。
2. 第二步，将中間結點到最後的結點進行反轉，如上圖的第一步。
3. 第三步，将反轉之後連結清單的頭節點連結在未反轉連結清單的頭節點之後，然後兩個連結清單同時往後走按照第一步的做法以此循環，直到反轉之後的連結清單走到空。

4. 解題代碼

/**
 * 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) {
    	//注釋1
        if(head == nullptr || head -> next == nullptr || head->next->next == nullptr)
        {
            return;
        }
        
        //注釋2
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast -> next)
        {
            fast = fast -> next  -> next;
            slow = slow -> next;
        }
        //注釋3
        ListNode *HNode = slow -> next;
        slow -> next = nullptr;
        ListNode* Node = nullptr;
        ListNode* cur = HNode;
        ListNode* Next = cur -> next;
   
        cur -> next = Node;
        while(Next)
        {
            Node = cur;
            cur = Next;
            Next = cur -> next;
            cur -> next = Node;
        }
        //注釋4
        ListNode *CurHead = head;
        ListNode *NewHead = cur;
        ListNode *Next1 = head;
        ListNode *Next2 = NewHead;
        while(Next2)
        {
            Next1 = CurHead -> next;
            Next2 = NewHead -> next;
            CurHead -> next = NewHead;
            NewHead -> next = Next1;
            CurHead = Next1;
            NewHead = Next2;
        }
    }
};
           

5. 代碼注釋詳解

1. 注釋1：如果

   節點數小于三個則直接傳回

   ，排列方式已經滿足題目要求。
2. 注釋2：

   快慢指針找中間結點

   ，并

   将中間節點的前一個結點指向空

   。
3. 注釋3：将

   中間結點到最後結點進行反轉

   。
4. 注釋4：按照圖解的方法将前後兩個連結清單進行重排列，當

   反轉之後的連結清單周遊到空時排列結束

   。

   合并有序連結清單算法複雜度為：

• 時間複雜度：O(n)
• 空間複雜度：O(1)

1.如有錯誤或者沒能了解的地方，請及時評論或者私信，及時修改更新

。

2.會持續更新相關連結清單高頻題目，分類專欄—資料結構

。