算法与数据结构基础 – 链表(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题：
