Linked List
链表
Tip:
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表的优点是动态大小和高效的插入和删除操作，但缺点是随机访问速度较慢。
对于链表题，我们要勤画图，敢于用变量，善用递归，保持思路清晰。
1. 合并两个有序链表
本题要求将两个有序链表合并为一个新的有序链表。
这里我们可以使用递归的方法来解决这个问题，递归的思路是最后为 null 时返回上一级， 然后比较两个链表的头节点，较小的节点作为新的链表的头节点，然后递归地合并剩下的部分。
Tip:
递归的思路是：
- 如果 list1 为空，返回 list2；
- 如果 list2 为空，返回 list1；
- 如果 list1 的头节点小于等于 list2 的头节点，将 list1 的头节点作为新的链表的头节点， 然后递归地合并 list1.next 和 list2；
- 否则，将 list2 的头节点作为新的链表的头节点， 然后递归地合并 list1 和 list2.next。
var mergeTwoLists = function(list1, list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1.val <= list2.val) {
// list1 的头节点较小（或相等），那下面继续合并的就是 list1.next 和 list2
list1.next = mergeTwoLists(list1.next, list2); // 递归合并 list1.next 和 list2
return list1; // 返回 list1 作为合并后的头
} else {
// list2 的头节点较小（或相等），那下面继续合并的就是 list1 和 list2.next
list2.next = mergeTwoLists(list1, list2.next); // 递归合并 list1 和 list2.next
return list2; // 返回 list2 作为合并后的头
}
};
2. 反转链表
反转链表是一个经典的链表操作，要求将链表的节点顺序反转。 我们可以递归直到链表的末尾，然后在调用栈中逐层返回时，反转指针的方向。
Tip:
反转链表的思路是：
- 如果链表为空或只有一个节点，直接返回链表；
- 递归地反转链表的后半部分；
- 将当前节点的 next 指针指向前一个节点；
- 返回新的头节点。
var reverseList = function(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
// 将当前节点的下一个节点的 next 指向当前节点
head.next.next = head;
head.next = null;
return newHead;
};
3. 反转链表 II
反转链表 II 要求反转链表的部分区间，给定一个头节点和两个整数 m 和 n，要求反转从位置 m 到 n 的链表。 为了更好理解，我们可以用迭代的方法来解决这个问题。
Tip:
反转链表 II 的思路是：
- 找到反转区间的前一个节点和后一个节点；
- 反转区间内的链表；
- 将前一个节点的 next 指向反转后的头节点，将反转后的尾节点的 next 指向后一个节点。
- 返回新的头节点。
var reverseBetween = function(head, left, right) {
if (!head || left === right) return head;
// 创建一个虚拟头节点，方便处理边界情况（链表题常用）
let dummy = new ListNode(0, head);
let prev = dummy;
// 找到反转区间的前一个节点
for (let i = 1; i < left; i++) {
prev = prev.next;
}
let curr = prev.next;
let next = null;
// 反转链表
for (let i = 0; i < right - left; i++) {
next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
};
4. 环形链表
环形链表是一个特殊的链表，要求判断链表中是否存在环。 这种题的思路就是使用快慢指针，快指针每次走两步，慢指针每次走一步， 如果链表中存在环，快指针和慢指针一定会相遇。（可以理解为小学生都会的追及问题 hhh）
var hasCycle = function(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (!fast || !fast.next) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
};
5. 稍微上难度！K 个一组翻转链表
本题要求将链表每 k 个节点一组进行翻转，如果最后一组的节点数不足 k，则不翻转。 这个题的思路就是对于每 k 个节点进行翻转，然后将翻转后的链表连接起来。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if (!head || k <= 1) {
return head;
}
// 创建一个哑节点，方便处理头节点的变化
let dummy = new ListNode(0, head);
// groupPrev 指向当前 k-group 的前一个节点
// 初始时，它是哑节点
let groupPrev = dummy;
while (true) {
// 1. 检查是否有足够的节点（k 个）来进行反转
let kthNode = groupPrev;
for (let i = 0; i < k; i++) {
kthNode = kthNode.next;
if (!kthNode) {
// 剩余节点不足 k 个，不需要反转，直接返回 dummy.next
// groupPrev.next 已经正确指向剩余部分的头部
return dummy.next;
}
}
// 此时 kthNode 是当前 k-group 的尾节点
// 2. 记录下一组的头节点
let groupNext = kthNode.next;
// 3. 反转当前的 k-group
// k-group 的头节点是 groupPrev.next
// k-group 的尾节点是 kthNode
// 反转后，原来的头变成尾，原来的尾变成头
let prevInSub = groupNext; // 反转后，当前组的（新）尾节点的 next 指针将指向 groupNext
let currInSub = groupPrev.next; // 当前 k-group 的头节点，也是反转过程中的当前节点
// 标准的链表反转过程，反转从 currInSub 到 kthNode (包含 kthNode) 的部分
// 或者说，反转的节点直到 currInSub 变成 groupNext
while (currInSub !== groupNext) {
let tempNext = currInSub.next;
currInSub.next = prevInSub;
prevInSub = currInSub;
currInSub = tempNext;
}
// 反转完成后, prevInSub 是当前 k-group 反转后的新头节点
// 4. 将反转后的 k-group 重新连接回主链表
let originalGroupHead = groupPrev.next;
groupPrev.next = prevInSub;
groupPrev = originalGroupHead;
}
return head;
};
6. 删除链表的倒数第 N 个节点
本题要求删除链表的倒数第 N 个节点。 我们可以使用快慢指针的方法，快指针先走 n 步，然后慢指针和快指针一起走， 那么当快指针走到链表的末尾时，慢指针正好在要删除的节点的前一个节点。
Tip:
删除链表的倒数第 N 个节点的思路是：
- 快指针先走 n 步；
- 快慢指针一起走，直到快指针到达链表的末尾；
- 慢指针的下一个节点就是要删除的节点，删除它。
- 返回链表的头节点。
var removeNthFromEnd = function(head, n) {
// 创建一个虚拟头节点，方便处理边界情况（哨兵节点）
let dummy = new ListNode(0, head);
let fast = dummy;
let slow = dummy;
// 快指针先走 n 步
for (let i = 0; i < n + 1; i++) {
fast = fast.next;
}
// 快慢指针一起走，直到快指针到达链表的末尾
while (fast) {
fast = fast.next;
slow = slow.next;
}
// 慢指针的下一个节点就是要删除的节点
slow.next = slow.next.next;
return dummy.next;
};
7. 删除排序链表中的重复元素 II
本题要求删除排序链表中的重复元素。
思路就是一次遍历链表，使用一个指针来记录当前节点的下一个节点，
如果下一个节点的值和下下个节点的值相同，就将当前节点的 next 指针指向下下个节点，
否则就将当前节点的 next 指针指向下一个节点。
Tip:
删除排序链表中的重复元素 II 的思路是：
- 创建一个虚拟头节点，方便处理边界情况；
- 使用一个指针来记录当前节点的下一个节点；
- 如果下一个节点的值和下下个节点的值相同，就将当前节点的 next 指针指向下下个节点；
- 否则就将当前节点的 next 指针指向下一个节点。
- 返回链表的头节点。
var deleteDuplicates = function(head) {
// 如果链表为空或只有一个节点，则不可能有重复，直接返回
if (!head || !head.next) {
return head;
}
// 创建一个哨兵节点，指向原始头节点，方便处理头节点可能被删除的情况
const dummy = new ListNode(0, head); // 可以用任何与节点值不同的值
let cur = dummy;
while (cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
const x = cur.next.val;
while (cur.next && cur.next.val === x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
};
8. 旋转链表
这题说是循环旋转，但其实本质上是将尾部向前数第 K 个元素作为头，原来的头接到原来的尾上
Tip:
旋转链表的思路是：
- 计算链表的长度；
- 将 k 对链表长度取模，得到实际需要旋转的步数；
- 找到新的头节点和尾节点；
- 将尾节点的 next 指向原来的头节点；
- 返回新的头节点。
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) return head;
// 计算链表的长度
let length = 1;
let tail = head;
while (tail.next) {
tail = tail.next;
length++;
}
// 将 k 对链表长度取模，得到实际需要旋转的步数
k %= length;
// 如果 k 为 0，说明不需要旋转，直接返回头节点
if (k === 0) return head;
// 找到新的头节点和尾节点
let newTail = head;
for (let i = 1; i < length - k; i++) {
newTail = newTail.next;
}
let newHead = newTail.next;
// 将尾节点的 next 指向原来的头节点
tail.next = head;
// 将新的尾节点的 next 指向 null
newTail.next = null;
return newHead;
};