一种线性数据结构。包含单向链表和双向链表。
单向链表的结构，操作（插入、删除和遍历）及其时间复杂度：
通常使用head节点表示整个链表。
插入：O(1)
删除：O(N)需要从head开始查找被删除节点的prev节点
按索引访问：O(N)
作为基础数据结构，相关的题目有很多，做了一部分，总结如下：
1. 特别注意NULL检查，有时候需要检查当前节点，有时候需要检查当前节点的NEXT节点；
2. 写代码之前先手工测试几个典型的测试案例。比如，空链表等；
3. 迭代过程中巧妙使用多个指针一起走，典型地比如，两个指针一起走，一个每次一步，快的每次两步；或者一个指针先走K步之后两个指针一起走，等；
4. 适当地借助DUMMY节点，能事半功倍；
5. 很多情况下，都是需要保存当前节点的前一个节点的。
典型题目：
160. Intersection of Two Linked Lists
19. Remove Nth Node From End of List
430. Flatten a Multilevel Doubly Linked List
138. Copy List with Random Pointer
引用：
网友评论