文章目录链表专题JS 实现原理与高频算法题总结1.使用js语法写链表的注意点1.1链表的结构体1.2 使用js连成一个链表1.3 头节点 head 的含义1.4 JS 中没有指针但有对象引用1.5 js中变量保存的是节点引用不是节点副本1.6 创建一个链表(头插法、尾插法)1.7 链表题常见注意点节点比较、dummy 虚拟头节点1.8 双向链表2.链表高频题实战2.1 力扣 160相交链表2.2 力扣 206反转链表2.3 力扣 21合并两个有序链表2.4 力扣 19删除链表的倒数第 N 个节点2.5 力扣 25K 个一组翻转链表链表专题JS 实现原理与高频算法题总结1.使用js语法写链表的注意点1.1链表的结构体在 c 语言中,使用结构体 struct 实现structListNode{intval;structListNode*next;};在 js 中,链表节点其实就是对象JS 里的链表节点 一个带 val 和 next 的对象functionListNode(val,next){this.val(valundefined?0:val)this.next(nextundefined?null:next)}如果不写 nextnull,默认就是 undefined其中的一个节点constnode1newListNode(1)console.log(node1){val:1,next:null}1.2 使用js连成一个链表constnode1newListNode(1)constnode2newListNode(2)constnode3newListNode(3)node1.nextnode2 node2.nextnode3node1-node2-node3-null此时打印 node1,也就是表头console.log(node1)ListNode{val:1,next:ListNode{val:2,next:ListNode{val:3,next:null}}}可以想象简化为,ListNode表示的是链表节点类的实例{val:1,next:{val:2,next:{val:3,next:null}}}1.3 头节点 head 的含义head 是链表入口不一定永远是原来的第一个节点。head 本身只是一个变量它保存的是第一个节点对象的引用并不是整条链表本身。constheadnode1//如果头结点要换来换去就用 let1.4 JS 中没有指针但有对象引用let p head //遍历链表 let p head while (p ! null) { console.log(p.val) p p.next }1.5 js中变量保存的是节点引用不是节点副本let p head指的是 p 和 head 都指向都一个节点对象// 链表是 1-2-3// node1 是头结点letpnode1;pp.next;console.log(p.val);console.log(node1.val);输出结果:2 1修改了节点的 next,才会改变链表p.nextnull //直接从头结点那里断开了1.6 创建一个链表(头插法、尾插法)functionListNode(val,next){this.val(valundefined?0:val)this.next(nextundefined?null:next)}constheadnewListNode(1)head.nextnewListNode(2)head.next.nextnewListNode(3)给定一个数组分别使用头插法和尾插法实现创建一个链表// 给定一个数组将这个数组初始化一个链表分别用头插法和尾插法初始化// 给定数组[1,5,4,8]// 头插法预期8-4-5-1// 尾插法预期1-5-4-8//链表数据结构functionListNode(val,next){this.valval;this.nextnext;}//头插法创建链表functionCreatListNodeByHead(arr){// 创建一个头节点letheadnewListNode(0,null);for(leti0;iarr.length;i){// 创建一个空节点letpnewListNode(arr[i],null);p.nexthead.next;head.nextp;}returnhead;}//尾插法创建链表functionCreatListNodeByTail(arr){// 创建一个头节点letheadnewListNode(0,null);// 创建一个尾指针记录最后一个元素的位置lettailhead;for(leti0;iarr.length;i){// 创建一个空节点letpnewListNode(arr[i],null);tail.nextp;tailp;}returnhead;}//遍历链表functionTravelListNode(head){letphead.next;while(p!null){console.log(p.val);pp.next;}}//开始测试constarr[1,5,4,8];letheadCreatListNodeByHead(arr);TravelListNode(head);lethead1CreatListNodeByTail(arr);TravelListNode(head1);//结束测试845115481.7 链表题常见注意点节点比较、dummy 虚拟头节点比较节点要用 ,这是比较是否是同一个节点对象,而不是比较值多用 dummy 虚拟头节点constdummynewListNode(0)letcurdummyreturndummy.next好处是用老判断“头节点是不是空”“第一个节点怎么连”。1.8 双向链表双向链表数据结构,多了一个prev指针指向前一个链表节点functionDListNode(val){this.valval;this.prevnull;this.nextnull;}双向链表的尾插法跟单链表的尾插法不一样的点就是需要单独维护一下向前指向的指针也不难// 双向链表数据结构functionDListNode(val,pre,next){this.valval;this.prepre;this.nextnext;}// 尾插法创建双向链表,旧的尾节点指向新的尾节点functionCreatDListNodeByTail(arr){letheadnewDListNode(0,null,null);lettailhead;//尾插创建双向链表for(leti0;iarr.length;i){letpnewDListNode(arr[i],null,null);tail.nextp;p.pretail;tailp;}returnhead;}2.链表高频题实战2.1 力扣 160相交链表/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } *//** * param {ListNode} headA * param {ListNode} headB * return {ListNode} */vargetIntersectionNodefunction(headA,headB){// 得到 A 链表的长度 时间复杂度是 o(n)// 得到 B 链表的长度 时间复杂度是 o(n)// 做差得到长度差,然后再一起移动,直到一个走到空还是没找到,即不存在,否则仍然存在// 整体的时间复杂度是 o(n)lettempAheadA;lettempBheadB;letlengthA0;letlengthB0;letchazhi0;letpAheadA;letpBheadB;while(tempA!null){lengthA;tempAtempA.next;}while(tempB!null){lengthB;tempBtempB.next;}console.log(lengthA);if(lengthAlengthB){chazhilengthA-lengthB;while(chazhi--){pApA.next;}while(pB!null){if(pApB)returnpA;else{pApA.next;pBpB.next;}}}else{chazhilengthB-lengthA;while(chazhi--){pBpB.next;}while(pA!null){if(pApB)returnpA;else{pApA.next;pBpB.next;}}}returnnull;};2.2 力扣 206反转链表/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } *//** * param {ListNode} head * return {ListNode} */varreverseListfunction(head){// 定义一个 cur 定义一个 pre pre 指向 null//首先定义了一个 pre节点,值是链表的第一个节点,指向了 null// 首先得排除一下这个链表有没有两个节点if(headnull||head.nextnull)returnhead;letprehead;letcurhead.next;//得把头结点断开,否则双向链表了head.nextnull;while(cur!null){letpcur.next;cur.nextpre;precur;curp;}returnpre;};2.3 力扣 21合并两个有序链表/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } *//** * param {ListNode} list1 * param {ListNode} list2 * return {ListNode} */varmergeTwoListsfunction(list1,list2){//如果两个链表中有空的直接返回另一个即可if(list1null)returnlist2;if(list2null)returnlist1;//创建一个虚拟的头节点 dummy,两两比较插入letdummynewListNode(0,null);letpdummy;letp1list1;letp2list2;while(p1!nullp2!null){if(p1.valp2.val){p.nextp1;pp.next;p1p1.next;}else{p.nextp2;pp.next;p2p2.next;}}//此时有一整条链表已经加入到了新链表中,将剩余部分加回while(p1!null){p.nextp1;pp.next;p1p1.next;}while(p2!null){p.nextp2;pp.next;p2p2.next;}returndummy.next;};2.4 力扣 19删除链表的倒数第 N 个节点/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } *//** * param {ListNode} head * param {number} n * return {ListNode} */varremoveNthFromEndfunction(head,n){//一个 o(n)的方法,利用两个指针,一个先走 n 步,然后一起移动,先走的指向空之后,后走的那个指向的就是倒数第 n 个节点lettempNn;letfasthead;letslowhead;letpreundefined;while(tempN--){fastfast.next;}while(fast!null){fastfast.next;preslow;slowslow.next;}// 有可能要删除的结点就是倒数第一个节点,所以要维护一个pre// 如果要删除的是第一个节点,headhead.nextif(slowhead){headhead.nextreturnhead;}if(slow.nextnull){pre.nextnull;}else{pre.nextslow.next;}returnhead;};2.5 力扣 25K 个一组翻转链表/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } *//** * param {ListNode} head * param {number} k * return {ListNode} */varreverseKGroupfunction(head,k){//处理一些特殊的情况if(headnull||head.nextnull)returnhead;// 创建一个虚拟头结点letdummynewListNode(0,null);dummy.nexthead;letenddummy.next;letnum1;//每次要连接的头和尾letlinkheaddummy;letlinktailnull;letstartnull;while(end!null){// 翻转开始的记录if(num1)startend;//什么时候要翻转?if(numk){//翻转要开始的地方//记录linktaillinktailend.next;//断开链表end.nextnull;// 翻转从 start 开始,从当前的 end 结束letprenull;letcurstart;while(cur!null){letpcur.next;cur.nextpre;precur;curp;}//翻转成功 pre 指向了翻转后的尾部linkhead.nextend;start.nextlinktail;// 更新 linkheadlinkheadstart;//更新 start 和 endstartlinktail;//更不更新都行endlinktail;//更新 numnum1;continue;}num;endend.next;}returndummy.next;};