算法與數據結構基礎 – 鏈表(Linked List)
- 2019 年 10 月 3 日
- 筆記
鏈表基礎
鏈表(Linked List)相比數組(Array),物理存儲上非連續、不支持O(1)時間按索引存取;但鏈表也有其優點,靈活的內存管理、允許在鏈表任意位置上插入和刪除節點。單向鏈表結構一般如下:
//Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };
相關LeetCode題:
鏈表增刪改查
要完成鏈表節點的查找、插入、刪除與修改,需要特別留意前後指針的修改、空指針的處理。總得來說鏈表增刪改查分三步:1/定義結束條件(一般為到達鏈表尾) 2/遍歷鏈表 3/遍歷過程中完成增刪改查。
一些情況下會用啞節點(dummy node)來更方便對鏈表增刪改查,這有時可以減少代碼量。比如 LeetCode題目 203. Remove Linked List Elements:
// 203. Remove Linked List Elements ListNode* removeElements(ListNode* head, int val) { ListNode* dummy=new ListNode(0); dummy->next=head; ListNode* cur=dummy; while(cur->next!=NULL){ if(cur->next->val==val) cur->next=cur->next->next; else cur=cur->next; } return dummy->next; }
以上如果不使用dummy node,如果head是要被刪除的節點,則需要特殊判斷和處理,使用dummy node則化解了這個問題。
相關LeetCode題:
203. Remove Linked List Elements 題解
876. Middle of the Linked List 題解
83. Remove Duplicates from Sorted List 題解
82. Remove Duplicates from Sorted List II 題解
1019. Next Greater Node In Linked List 題解
1171. Remove Zero Sum Consecutive Nodes from Linked List 題解
也可以用遞歸的方式遍歷鏈表,但這種方式會重複訪問節點,時間複雜度比O(n)高很多。
相關LeetCode題:
反轉/旋轉鏈表
反轉(reverse)鏈表與旋轉(rotate)鏈表是考量鏈表操作的經典題目,最是考驗做題人對鏈表節點邏輯關係的了解程度和是否能靈活處理指針。
相關LeetCode題:
25. Reverse Nodes in k-Group 題解
環形鏈表
處理環形鏈表問題,常常用到雙指針(Two Pointers)、快慢指針,例如 LeetCode題目 141. Linked List Cycle:
// 141. Linked List Cycle bool hasCycle(ListNode *head) { if(head==NULL) return false; ListNode* p=head; ListNode* pp=head; while(pp->next!=NULL&&pp->next->next!=NULL){ p=p->next; pp=pp->next->next; if(p==pp) return true; } return false; }
相關LeetCode題:
708. Insert into a Cyclic Sorted List 題解
多鏈表處理
多鏈表的增刪改、合併,與單鏈表的處理方式一樣,只是增加了對多個鏈表的遍歷。
相關LeetCode題:
160. Intersection of Two Linked Lists 題解
鏈表排序
對鏈表進行排序一般指原址排序,即修改節點指針指向、而不修改節點的值。對鏈表進行歸併排序(Merge Sort),平均時間複雜度為O(nlogn),相比其他排序方法,歸併排序在平均時間複雜度上是較優的方法。
相關LeetCode題: