合并有序鏈表
- 1. 題目描述
- 2. 題目鏈接
- 3. 題目剖析
- 3.1剖析圖示
- 3.2 圖示詳解
- 4. 解題代碼
- 5. 代碼注釋詳解
滿難度系數
* * * * *，此題難度系數* * *，
滿考頻熱度* * * * *，此題熱度* * * * *，
1. 題目描述
2. 題目鏈接
- 牛客題目鏈接重排鏈表
3. 題目剖析
- 重排鏈表方式是從兩頭到中間交錯重排，假如鏈表有4個結點，
重排方式是1->4->2->3， - 主要考察對鏈表的基本操作，要處處小心，
以免越界考的知識點有：快慢指標找中間結點，反轉鏈表，鏈表鏈接等知識點， - 快慢指標找中間結點和反轉鏈表在之前題解有過詳解：反轉鏈表link
- 具體操作如下圖解，詳細程序如下，
3.1剖析圖示
3.2 圖示詳解
- 第一步，先利用快慢指標的思想找到中間結點，并將中間結點作為一個新鏈表的頭進行記錄，
- 第二步，將中間結點到最后的結點進行反轉，如上圖的第一步，
- 第三步，將反轉之后鏈表的頭節點鏈接在未反轉鏈表的頭節點之后，然后兩個鏈表同時往后走按照第一步的做法以此回圈，直到反轉之后的鏈表走到空，
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：如果
節點數小于三個則直接回傳，排列方式已經滿足題目要求， - 注釋2：
快慢指標找中間結點，并將中間節點的前一個結點指向空， - 注釋3：將
中間結點到最后結點進行反轉， - 注釋4：按照圖解的方法將前后兩個鏈表進行重排列，當
反轉之后的鏈表遍歷到空時排列結束，
合并有序鏈表演算法復雜度為：
- 時間復雜度：O(n)
- 空間復雜度：O(1)
1.如有錯誤或者沒能理解的地方，請及時評論或者私信，及時修改更新，
2.會持續更新相關鏈表高頻題目，分類專欄—資料結構，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274829.html
標籤：其他
上一篇：2021 年“認證杯”數學中國數學建模網路挑戰賽 B題解題思路
下一篇：linux安裝nginx