算法與數據結構基礎 – 鏈表(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題:

707. Design Linked List  題解

 

鏈表增刪改查

要完成鏈表節點的查找、插入、刪除與修改,需要特別留意前後指針的修改、空指針的處理。總得來說鏈表增刪改查分三步: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  題解

328. Odd Even Linked List  題解

1019. Next Greater Node In Linked List  題解

1171. Remove Zero Sum Consecutive Nodes from Linked List  題解 

 

也可以用遞歸的方式遍歷鏈表,但這種方式會重複訪問節點,時間複雜度比O(n)高很多。

 

相關LeetCode題:

24. Swap Nodes in Pairs  題解

 

反轉/旋轉鏈表

反轉(reverse)鏈表與旋轉(rotate)鏈表是考量鏈表操作的經典題目,最是考驗做題人對鏈表節點邏輯關係的了解程度和是否能靈活處理指針。

 

相關LeetCode題:

206. Reverse Linked List  題解

92. Reverse Linked List II  題解  

61. Rotate List  題解

25. Reverse Nodes in k-Group  題解

143. Reorder List  題解

 

環形鏈表

處理環形鏈表問題,常常用到雙指針(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題:

141. Linked List Cycle  題解

142. Linked List Cycle II  題解

708. Insert into a Cyclic Sorted List  題解

 

多鏈表處理

多鏈表的增刪改、合併,與單鏈表的處理方式一樣,只是增加了對多個鏈表的遍歷。

 

相關LeetCode題:

160. Intersection of Two Linked Lists  題解

21. Merge Two Sorted Lists  題解

2. Add Two Numbers  題解

445. Add Two Numbers II  題解

 

鏈表排序

對鏈表進行排序一般指原址排序,即修改節點指針指向、而不修改節點的值。對鏈表進行歸併排序(Merge Sort),平均時間複雜度為O(nlogn),相比其他排序方法,歸併排序在平均時間複雜度上是較優的方法。

 

相關LeetCode題:

147. Insertion Sort List  題解

148. Sort List  題解