刷題記錄---連結清單總結
- 連結清單性質
-
- leetcode中節點定義
- 連結清單操作(可作為輪子)
-
- 連結清單反轉（單向連結清單）
- 連結清單拼接
- 連結清單排序
- 連結清單操作技巧
-
- 快慢指針
- 虛拟頭節點
- 注意切斷連結清單
- 算法執行個體
連結清單性質
連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。
連結清單由一系列結點（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。
單連結清單隻有一個後驅節點next，雙向連結清單還會有一個前驅節點pre。
連結清單的基本操作：
- 插入
tempnode = cur->next;
cur->next = insertNode;
insertNode->next = tempnode
- 删除
tempnode = precur;
precur->next = precur->next->next;
free(tempnode);
- 周遊
目前指針 = 頭指針
while 目前節點不為空 {
print(目前節點)
目前指針 = 目前指針.next
}
leetcode中節點定義
結構中定義了構造函數，用于構造帶有初始值的節點
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) {}
};
連結清單操作(可作為輪子)
連結清單反轉（單向連結清單）
方法一：前序周遊
ListNode* reverse(ListNode* head)
{
ListNode* pre = nullptr;//設定一個尾節點指向的空指針
while(ListNode* != nullptr)
{
ListNode* next = head->next;//記錄此時節點的下一個節點的位置
head->next = pre;//将此節點的節點指向前一個節點
pre = head; //将前一個節點指向這時的節點
head = next; //将這時的節點指向下一個節點、也就是将兩個幾點都往後移動一位
}
return pre;//這裡是因為head已經指向了空指針，隻有pre指向的是連結清單的最後一個位置
}
方法二：後續周遊，遞歸調用
ListNode* function2(ListNode* head)//遞歸解法---後續周遊
{
if(head == nullptr || head->next == nullptr){return head;}//一直走到最後一個節點後傳回，作為反轉連結清單的頭節點
ListNode* cur = function2(head->next);//cur一直指向的都是最後一個節點
head->next->next = head;//将原本順序的下一節點反置
head->next = nullptr;//将這一節點指向下一節點的指針賦空
return cur;//傳回反轉的頭節點
}
方法三：當有前後兩個節點，頭節點和尾節點的下一個節點（建議畫圖了解）
ListNode* reversePart(ListNode* head, ListNode* tail) {
//添加一個尾節點，即在最後一個節點的最後再添加一個節點
//head 為連結清單第一個節點，tail 為最後一個節點後面一個節點
if (head == tail || head->next == tail) {
return head;
}
ListNode* p, *q;
q = tail;
while (head != tail) {
p = head->next; //q節點是用來存儲head的下一個節點位置
head->next = q; //q是head要指向的節點位置
q = head; //每次更新完需要把指向節點的位置一刀下一次要指向的位置
head = p; //将head往後移一次
}
return q;
}
連結清單拼接
合并了兩個有序連結清單—結果還是有序
遞歸調用：
//時間複雜度和空間複雜度都是O(n+m)
ListNode* function1(ListNode* l1,ListNode *l2)//遞歸調用也需要到最後一個指針處,可以考慮承接節點的前一個節點
{
if(l1==nullptr) //如果有一個節點是空了，直接傳回另一個節點就可以
{return l2;}
if(l2==nullptr)
{return l1;}
if(l1->val < l2->val) //如果兩個值的大小不等的話，以小的節點為起始節點，并計算目前連結清單的下一個節點和另一個連結清單節點值
{
l1->next = function1(l1->next,l2); //接着找下一個節點
return l1;
}
if(l1->val > l2->val)
{
l2->next = function1(l1,l2->next);
return l2;
}
}
不使用遞歸調用，使用疊代：
ListNode* function2(ListNode* l1,ListNode* l2)
{
ListNode* prehead = new ListNode(-1);
ListNode* pre = prehead;
//如果兩者由一個為空了，那麼後面的直接從另一個連結清單擷取
while(l1!=nullptr && l2!=nullptr)//起初假設兩者都不為空
{
if(l1->val > l2->val) //比較值的大小，小的值放到節點後，每次隻放進一個
{
pre->next = l1;
l1 = l1->next;
}
else
{
pre->next = l2;
l2= l2->next;
}
pre = pre->next; //記錄目前拼接連結清單的最後一個節點
}
pre->next = l1 == nullptr ? l2 : l1;//如果後續連結清單有一個沒有值了，就直接讀取另一個連結清單的值(因為兩者已經拍好序了)
return prehead->next;//傳回頭節點的下一個節點
}
連結清單排序
無序連結清單按照大小排序
紅黑樹，利用set容器實作：
multiset<int> slist;
ListNode* res = head;
ListNode* result = head;
while(head != nullptr)
{
slist.insert(head->val);
head = head->next;
}
for(auto it = slist.begin(); it!= slist.end();it++)
{
res->val = *it;
res = res->next;
}
return result;
歸并排序—将連結清單二分，直至不能再劃分，再通過子連結清單按大小拼接
if(head == nullptr || head->next == nullptr){return head;}
ListNode* slow = head,*fast = head;
while(!fast->next && !fast->next->next)//這裡和判斷是否是回文連結清單的條件還不一樣，靈活運用
{
slow = slow->next;//slow到達中點的前面一個
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
return merge(sortList(head),sortList(fast));//用到的子函數
ListNode* merge(ListNode* l1,ListNode* l2)
{
ListNode res(0);
ListNode* ptr = &res;
while(l1 && l2)
{
if(l1->val > l2->val)
{
ptr->next = l2;
l2 = l2->next;
}
else
{
ptr->next = l1;
l1 = l1->next;
}
ptr = ptr->next;
}
ptr->next = l1 == nullptr ? l2 : l1;
return res.next;
}
堆排序，利用stl中的優先隊列，其底層是堆排序算法
priority_queue<int,vector<int>,greater<int>> worker;
auto sub = head;
while(sub)
{
worker.push(sub->val);//每次放進去都是把最小的放到最前面
sub=sub->next;
}
sub = head;
while(sub)
{
sub->val = worker.top();
worker.pop();
sub = sub->next;
}
return head;
連結清單操作技巧
快慢指針
設定一個快指針一個慢指針，每次快指針走的步數是慢指針的兩倍，最後傳回慢指針就到達中點。
考慮一下幾種情況
到達中點指針
ListNode* head;
ListNode* fast = head,* slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
if(fast != nullptr){
slow = slow->next;
}
到達中心節點的前一個節點
while(fast->next != nullptr && fast->next->next != nullptr){
fast = fast->next->next;
slow = slow->next;//這時的slow始終會在中心節點的前一個節點
}
虛拟頭節點
新加一個虛拟頭節點友善操作
在反轉子連結清單的時候用到了
ListNode* virhead = new ListNode(0);
virhead->next = head;
注意切斷連結清單
在重排連結清單這一題需要把一個連結清單分割成兩個連結清單，需要把中間節點斷開，即先記錄中心節點的位置，再将中心節點前一個節點的next置為nullptr，利用快慢指針到中間節點的前一個節點。
算法執行個體
- 合并兩個有序連結清單
- 删除排序連結清單中的重複元素 II
- 删除排序連結清單中的重複元素
- 分隔連結清單
- 反轉連結清單 II
- 環形連結清單
- 環形連結清單 II
- 重排連結清單
- 排序連結清單
- 反轉連結清單
- 回文連結清單
![字元串求和問題[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)