LeetCodeHot100|链表总结

最近把leetcode的链表刷完了，所以想着来写一个关于链表的小结

刷过的题目表

相交链表、反转链表、回文链表、环形链表、环形链表二、两个合并有序链表、删除链表的倒数第N个结点、两两交换链表中的节点、K个一组翻转链表、随机链表的复制、排序链表、LRU缓存

这些都是关于链表的题目，在刷完这些题目之前，再来对对链表的基础知识做一个总结回顾，链表的这些操作是必须要会的，分别是初始化链表，插入节点，删除节点，访问节点，查找节点。首先来看如何初始化链表。

这里有一张链表和数组在内存中存储的图，方便大家理解。

初始化链表

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */// 初始化各个节点ListNode*n0=newListNode(1);ListNode*n1=newListNode(3);ListNode*n2=newListNode(2);ListNode*n3=newListNode(5);ListNode*n4=newListNode(4);// 构建节点之间的引用n0->next=n1;n1->next=n2;n2->next=n3;n3->next=n4;

从这里可以看出，构建链表主要是通过两步，第一步是构建各个节点，第二步是构建各个节点之间的引用。

插入节点

// 在链表n0之后插入节点 Pvoidinsert(ListNode*n0,ListNode*p){ListNode*n1=n0->next;p->next=n1;n0->next=p;}

入上图所示，如果想在两个节点之间插入一个节点的话，需要改变两个指针的指向，分别是修改n0和p指针的指向，在n0与n1之间插入，时间复杂度为O(1)

删除节点

/* 删除链表的节点 n0 之后的首个节点 */voidremove(ListNode*n0){if(n0->next==nullptr)return;// n0 -> P -> n1ListNode*P=n0->next;ListNode*n1=P->next;n0->next=n1;// 释放内存deleteP;}

如上图所示，在链表中删除节点，只需要改变一个节点的引用（指针）即可

，虽然节点P仍然指向n1，但是遍历的时候已经找不到它了。

访问节点

// 访问链表中索引为 index 的节点ListNode*access(ListNode*head,intindex){for(inti=0;i<index;i++){if(head==nullptr)returnnullptr;head=head->next;}returnhead;}

在数组访问元素的时间复杂度是O(1),但是在链表中访问元素的复杂度为O(n),访问节点的效率低。程序在访问时需要从头节点出发，逐个往后便利，直到找到目标节点，也就是访问第i个节点需要i-1轮，时间复杂度为O(n).链表在内存中的真实布局类似下图.

查找节点

// 在链表中查找值为 target的首个节点intfind(ListNode*head,inttaget){intindex=0;while(head!=nullptr){if(head->val==target)returnindex;head=head->next;index++;}return-1;}

查找值为target 的节点，输出改节点在链表中的索引，这个过程也属于线性查找。了解完这些之后链表的一些基础操作就都知道了，前面讲的都是单向链表，其实链表还有其他的类型，比如环形链表，以及双向链表，如下图所示。