LeetCodeHot100|链表总结

最近把leetcode的链表刷完了所以想着来写一个关于链表的小结刷过的题目表相交链表、反转链表、回文链表、环形链表、环形链表二、两个合并有序链表、删除链表的倒数第N个结点、两两交换链表中的节点、K个一组翻转链表、随机链表的复制、排序链表、LRU缓存这些都是关于链表的题目在刷完这些题目之前再来对对链表的基础知识做一个总结回顾链表的这些操作是必须要会的分别是初始化链表插入节点删除节点访问节点查找节点。首先来看如何初始化链表。这里有一张链表和数组在内存中存储的图方便大家理解。初始化链表/* 初始化链表 1 - 3 - 2 - 5 - 4 */// 初始化各个节点ListNode*n0newListNode(1);ListNode*n1newListNode(3);ListNode*n2newListNode(2);ListNode*n3newListNode(5);ListNode*n4newListNode(4);// 构建节点之间的引用n0-nextn1;n1-nextn2;n2-nextn3;n3-nextn4;从这里可以看出构建链表主要是通过两步第一步是构建各个节点第二步是构建各个节点之间的引用。插入节点// 在链表n0之后插入节点 Pvoidinsert(ListNode*n0,ListNode*p){ListNode*n1n0-next;p-nextn1;n0-nextp;}入上图所示如果想在两个节点之间插入一个节点的话需要改变两个指针的指向分别是修改n0和p指针的指向在n0与n1之间插入时间复杂度为O(1)删除节点/* 删除链表的节点 n0 之后的首个节点 */voidremove(ListNode*n0){if(n0-nextnullptr)return;// n0 - P - n1ListNode*Pn0-next;ListNode*n1P-next;n0-nextn1;// 释放内存deleteP;}如上图所示在链表中删除节点只需要改变一个节点的引用指针即可虽然节点P仍然指向n1但是遍历的时候已经找不到它了。访问节点// 访问链表中索引为 index 的节点ListNode*access(ListNode*head,intindex){for(inti0;iindex;i){if(headnullptr)returnnullptr;headhead-next;}returnhead;}在数组访问元素的时间复杂度是O(1),但是在链表中访问元素的复杂度为O(n),访问节点的效率低。程序在访问时需要从头节点出发逐个往后便利直到找到目标节点也就是访问第i个节点需要i-1轮时间复杂度为O(n).链表在内存中的真实布局类似下图.查找节点// 在链表中查找值为 target的首个节点intfind(ListNode*head,inttaget){intindex0;while(head!nullptr){if(head-valtarget)returnindex;headhead-next;index;}return-1;}查找值为target 的节点输出改节点在链表中的索引这个过程也属于线性查找。了解完这些之后链表的一些基础操作就都知道了前面讲的都是单向链表其实链表还有其他的类型比如环形链表以及双向链表如下图所示。