【LeetCode Hot100】链表知识点集合

链表基础1.创建链表// 手动创建 1 - 2 - 3constn1newListNode(1);constn2newListNode(2);constn3newListNode(3);n1.nextn2;n2.nextn3;letheadn1;遍历链表模板letcurhead;while(cur){console.log(cur.val);curcur.next;}链表反转核心代码functionreverseList(head){letprevnull,curhead;while(cur){consttempcur.next;// 保存下一个cur.nextprev;// 反转指向prevcur;curtemp;}returnprev;}快慢指针找中点 / 环letslowhead,fasthead;while(fastfast.next){slowslow.next;fastfast.next.next;}// slow 是中点LeetCode Hot100160.相交链表给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。图示两个链表在节点 c1 开始相交题目数据 保证 整个链式结构中不存在环。注意函数返回结果后链表必须 保持其原始结构 。自定义评测评测系统 的输入如下你设计的程序 不适用 此输入intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。示例 1输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3输出Intersected at ‘8’解释相交节点的值为 8 注意如果两个链表相交则不能为 0。从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。— 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。示例 2输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1输出Intersected at ‘2’解释相交节点的值为 2 注意如果两个链表相交则不能为 0。从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2输出No intersection解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。这两个链表不相交因此返回 null 。提示listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]进阶你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案AC代码vargetIntersectionNodefunction(headA,headB){constjihenewSet()lettempheadAwhile(temp!null){jihe.add(temp)temptemp.next}tempheadBwhile(temp!null){if(jihe.has(temp)){returntemp}temptemp.next}returnnull};206.反转链表给你单链表的头节点 head 请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5]输出[5,4,3,2,1]示例 2输入head [1,2]输出[2,1]示例 3输入head []输出[]提示链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题AC代码varreverseListfunction(head){letprenullletcurheadwhile(cur){consttempcur.next cur.nextpre precur curtemp}returnpre};234.回文链表给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 105] 内0 Node.val 9进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题AC代码varisPalindromefunction(head){letarr[]lettempheadwhile(temp!null){arr.push(temp.val)temptemp.next}for(leti0,jarr.length-1;ij;i,j--){if(arr[i]!arr[j]){returnfalse}}returntrue};141.环形链表给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。示例 1输入head [3,2,0,-4], pos 1输出true解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出true解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出false解释链表中没有环。提示链表中节点的数目范围是 [0, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 。进阶你能用 O(1)即常量内存解决此问题吗AC代码varhasCyclefunction(head){letsetnewSet();while(head){if(set.has(head)){returntrue;}set.add(head);headhead.next;}returnfalse;};142.环形链表 Ⅱ给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引进阶你是否可以使用 O(1) 空间解决此题AC代码vardetectCyclefunction(head){letsetnewSet()while(head){if(set.has(head)){returnhead}set.add(head)headhead.next}returnnull};21.合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]提示两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列AC代码varmergeTwoListsfunction(list1,list2){if(list1null){returnlist2}elseif(list2null){returnlist1}elseif(list1.vallist2.val){list1.nextmergeTwoLists(list1.next,list2)returnlist1}else{list2.nextmergeTwoLists(list1,list2.next)returnlist2}};