Hot100-链表-JS

160.相交链表

160. 相交链表

已解答

简单

相关标签

相关企业

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• 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 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

实现思路

1. ​变量作用域优化​：

   • 在 if (lengthA > lengthB) 和 else 分支中，分别处理 l1 或 l2 的移动，避免混淆。
   • 在 while (l1 && l2) 循环中，统一检查 l1 === l2，逻辑更清晰。

2. ​合并逻辑分支​：

   • 将两个 if 分支的逻辑合并为一个通用的 while (l1 && l2) 循环，减少重复代码。

3. ​指针移动时机​：

   • 在计算长度后，先让较长的链表移动 diff 步，然后同时遍历两个链表，直到找到交点或遍历结束。

4. ​返回值修正​：

   • 无论哪个链表先走到交点，都返回 l1 或 l2（因为此时 l1 === l2）。

代码实现

var getIntersectionNode = function(headA, headB) {let l1 = headA;let l2 = headB;let lengthA = 0, lengthB = 0;// 计算链表 A 的长度while (l1) {l1 = l1.next;lengthA++;}// 计算链表 B 的长度while (l2) {l2 = l2.next;lengthB++;}// 重置指针l1 = headA;l2 = headB;// 让较长的链表先走差值步let diff = Math.abs(lengthA - lengthB);if (lengthA > lengthB) {while (diff--) {l1 = l1.next;}} else {while (diff--) {l2 = l2.next;}}// 同时遍历，寻找交点while (l1 && l2) {if (l1 === l2) {return l1; // 返回交点}l1 = l1.next;l2 = l2.next;}return null; // 无交点
};

 206.反转链表

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

var reverseList = function(head) {let prev = null; // 前驱节点let current = head; // 当前节点let temp; // 暂存当前节点的下一个节点while (current) {temp = current.next; // 暂存下一个节点current.next = prev; // 反转当前节点的指针prev = current; // 移动 prev 到当前节点current = temp; // 移动 current 到下一个节点}return prev; // 返回新的头节点
};

 234.回文链表

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) 空间复杂度解决此题？

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {boolean}*/
var isPalindrome = function(head) {// 获得长度，然后用栈的操作 前一半入栈 后一半出栈let stack1=[];let length=0let p=head;while(p){length++;p=p.next;}p=head;// 存储前一半的数for(let i=0;i<Math.floor(length/2);i++){stack1.push(p.val);p=p.next;}// 如果为奇数就跳过中间的数if(length%2===1){p=p.next; }// 现在p指针位于后一段的第一个数上// 比较后一段的数和前一段是否相等for(let i=0;i<Math.floor(length/2);i++){if(p.val===stack1.pop()){p=p.next;}else{return false;}}return true;
};

141.环形链表I

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 <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} head* @return {boolean}*/
var hasCycle = function(head) {let slow=head;let fast=head;while (fast && fast.next) {slow = slow.next;          // 慢指针走 1 步fast = fast.next.next;     // 快指针走 2 步if (slow === fast) return true; // 快慢指针相遇，有环}return false; // 快指针到达末尾，无环
};

142.环形链表II

142. 环形链表 II

已解答

中等

相关标签

相关企业

给定一个链表的头节点  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 <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

实现思路​

1. ​检测环​：

   • 使用快慢指针（slow 和 fast），如果它们相遇，说明有环。

2. ​找到环的起始节点​：

   • 相遇后，重新设置 ptr1 指向链表头部，ptr2 指向相遇点。
   • 然后 ptr1 和 ptr2 以相同速度移动，它们的交点就是环的起始节点。

3. ​**无环时返回 null**​：

   • 如果 fast 或 fast.next 为 null，说明链表无环，返回 null。

---

​为什么这样能找到环的起始节点？​​

• 设链表头到环起点的距离为 a，环起点到相遇点的距离为 b，相遇点到环起点的距离为 c。
• 快指针走的距离是慢指针的 2 倍：2(a+b)=a+b+k⋅(b+c)其中 k 是快指针在环内绕的圈数。
• 化简得：a+b=k⋅(b+c)a=(k−1)⋅(b+c)+c这意味着从链表头到环起点的距离 a 等于从相遇点再走 c 步的距离。
• 因此，当 ptr1（从头开始）和 ptr2（从相遇点开始）以相同速度移动时，它们会在环起点相遇。

代码实现

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} head* @return {ListNode}*/
var detectCycle = function (head) {let slow = head;let fast = head;while (fast && fast.next) {slow = slow.next;          // 慢指针走 1 步fast = fast.next.next;     // 快指针走 2 步if (slow === fast) {// 找到环后，重新定位指针找环的起始节点let ptr1 = head;let ptr2 = slow;while (ptr1 !== ptr2) {ptr1 = ptr1.next;ptr2 = ptr2.next;}return ptr1; // 返回环的起始节点}}return null; // 快指针到达末尾，无环
};

21.合并两个有序链表

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 <= 100
• l1 和 l2 均按 非递减顺序 排列

1. ​使用哑节点（Dummy Node）​​：

   • 哑节点是一个虚拟节点，用于简化链表操作。它作为合并后链表的起始点，避免处理头节点的特殊情况。

2. ​正确合并逻辑​：

   • 比较 l1 和 l2 的当前节点值，将较小的节点连接到 current.next。
   • 移动较小节点的指针（l1 或 l2）到下一个节点。
   • 移动 current 到新连接的节点。

3. ​处理剩余节点​：

   • 当其中一个链表遍历完后，直接将另一个链表的剩余部分连接到 current.next。

4. ​返回合并后的链表头节点​：

   • 返回 dummy.next，即合并后链表的真正头节点。

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} list1* @param {ListNode} list2* @return {ListNode}*/
function mergeTwoLists(l1, l2) {// 创建一个哑节点（dummy node）作为合并后链表的起始点let dummy = new ListNode(-1);let current = dummy;while(l1&&l2){if(l1.val<=l2.val){current.next=l1l1=l1.next}else{current.next = l2;l2 = l2.next;}current=current.next}// 将剩余的链表直接连接到合并后的链表if (l1 !== null) {current.next = l1;} else {current.next = l2;}// 返回合并后的链表头节点（跳过哑节点）return dummy.next;
}

 2.两数相加

2. 两数相加

 

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var addTwoNumbers = function (l1, l2) {let dummy = new ListNode(-1); // 哑节点let current = dummy;let carry = 0; // 进位while (l1 !== null || l2 !== null || carry !== 0) {// 获取当前节点的值（如果节点存在）let val1 = l1 ? l1.val : 0;let val2 = l2 ? l2.val : 0;// 计算当前位的和 + 进位let sum = val1 + val2 + carry;carry = Math.floor(sum / 10); // 计算新的进位current.next = new ListNode(sum % 10); // 创建新节点current = current.next; // 移动 current 指针// 移动 l1 和 l2 指针if (l1) l1 = l1.next;if (l2) l2 = l2.next;}return dummy.next; // 返回合并后的链表头节点
};

19.删除链表的倒数第n个节点

19. 删除链表的倒数第 N 个结点

已解答

中等

相关标签

相关企业

提示

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function (head, n) {// length为链表长度let length = 0;// p指向头节点let p = head// 计算链表长度while (p) {length++p = p.next}// 如果要删除的是头节点if (n === length) {return head.next;}// 找到倒数第 n+1 个节点p = headfor (let i = 1; i < length - n; i++) {p = p.next}// 删除倒数第 n 个节点p.next = p.next.next;return head
};

24.两两交换链表中的节点

24. 两两交换链表中的节点

 

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var swapPairs = function (head) {// 创建哑节点，简化头节点交换let dummy = new ListNode(0)dummy.next = headlet prev = dummywhile (prev.next && prev.next.next) {// 当前要交换的两个节点let first = prev.nextlet second = prev.next.next// 执行交换prev.next = second// 哑节点指向第二个节点first.next = second.next// 第一个节点指向第二个节点的下一个second.next = first  // 第二个节点指向第一个节点// 移动prev指针到下一对的前驱prev = first}return dummy.next
};