# 👉 链表应用
链表常见题目类型有：
- 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
- 链表的反转及其衍生题目
- 链表成环问题及其衍生题目
做链表处理类问题，把握住一个中心思想——处理链表的本质，是处理链表结点之间的指针关系。
# 合并
# 两个链表合并
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
思路：
两个链表如果想要合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，就能达到目的。因此需要一个针线把各个结点串连起来。
可以新建一个 listNode，对两个链表的节点进行对比，选择最小值串入..以此类推，直到其中一个链表结束，将另一个链表剩下的节点全部串入即可。
var mergeTwoLists = function(l1, l2) {
// 定义头结点，确保链表可以被访问到
let head = new ListNode();
// cur 这里就是咱们那根“针”
let cur = head;
while (l1 && l2) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
// 处理剩余链表
cur.next = !l1 ? l1 : l2;
// 返回起始结点
return head.next;
};
# 链表求和
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
var addTwoNumbers = function(l1, l2) {
if (!l1 && !l2) return null;
const dummy = new ListNode();
let cur = dummy;
let carry = 0;
const addSum = (l1, l2) => {
let sum = l1 + l2 + carry;
const newNode = new ListNode(sum % 10);
carry = Math.floor(sum / 10);
return newNode;
};
while (l1 || l2) {
let num1 = l1 ? l1.val : 0;
let num2 = l2 ? l2.val : 0;
cur.next = addSum(num1, num2);
cur = cur.next;
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
if (carry !== 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
};
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。(正序)
翻转再相加，然后对相加后的链表再翻转
var addTwoNumbers = function(l1, l2) {
if (!l1 && !l2) return null;
const reverse = (head) => {
if (!head) return [];
let prev = null;
let cur = head;
while (cur) {
let temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
};
const dummy = new ListNode();
let cur = dummy;
let carry = 0;
let reverseL1 = reverse(l1);
let reverseL2 = reverse(l2);
while (reverseL1 || reverseL2) {
let num1 = reverseL1 ? reverseL1.val : 0;
let num2 = reverseL2 ? reverseL2.val : 0;
let sum = num1 + num2 + carry;
cur.next = new ListNode(sum % 10);
carry = Math.floor(sum / 10);
reverseL1 = reverseL1 ? reverseL1.next : null;
reverseL2 = reverseL2 ? reverseL2.next : null;
cur = cur.next;
}
if (carry !== 0) {
cur.next = new ListNode(carry);
}
return reverse(dummy.next);
};
利用栈
var addTwoNumbers = function(l1, l2) {
let cur1 = l1;
let cur2 = l2;
let stack1 = [];
let stack2 = [];
while (cur1) {
stack1.push(cur1.val);
cur1 = cur1.next;
}
while (cur2) {
stack2.push(cur2.val);
cur2 = cur2.next;
}
let index1 = stack1.length - 1,
index2 = stack2.length - 1;
let cur = null;
let prev = new ListNode();
let carry = 0;
while (index1 >= 0 || index2 >= 0) {
let num1 = stack1[index1] ? stack1[index1] : 0;
let num2 = stack2[index2] ? stack2[index2] : 0;
let sum = num1 + num2 + carry;
prev = new ListNode(sum % 10);
carry = Math.floor(sum / 10);
prev.next = cur;
cur = prev;
index1--;
index2--;
}
if (carry !== 0) {
prev = new ListNode(carry);
prev.next = cur;
}
return prev;
};
# 删除
删除链表节点的基操：就是将需要删除的目标结点的前驱结点 next 指针往后指一格。
# 删除重复元素，保留一个
真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。输入: 1->1->2 输出: 1->2 输入: 1->1->1 输出: 1
在给定排序的链表时，判断当前节点和后面的节点是否重复，是则往后指一个。
var deleteDuplicates = function(head) {
let cur = head;
while (cur) {
// 当前结点和它后面一个结点值重复了，则将next指向next.next，然后继续cur和cur.next比较
if (cur.next && cur.val === cur.next.val) {
cur.next = cur.next.next;
} else {
// 若不重复，继续往下走
cur = cur.next;
}
}
return head;
};
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
# 善用 dummy - 删除所有重复元素不保留
为了更好的管理前驱和后继，可通过人造一个 dummy 结点，作为头结点的前驱结点，更方便处理。
其实在链表题中，经常会遇到这样的问题：链表的第一个结点，因为没有前驱结点，导致我们面对它无从下手。这时我们就可以用一个 dummy 结点来解决这个问题。
真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。
这一题较上面的区别是需要把所有重复数字的结点都删除，这个时候需要连前驱和后继给一起删掉。
var deleteDuplicates = function(head) {
// 构造头结点的前驱结点
const dummy = new ListNode();
// dummy 永远指向头结点
dummy.next = head;
let cur = dummy;
// 至少有两个结点
while (cur.next && cur.next.next) {
// 对 cur 后面的两个结点进行比较
if (cur.next.val === cur.next.next.val) {
// 记录重复值
let repeat = cur.next.val;
// 直接跳过这两个重复值，往后走
cur.next = cur.next.next.next;
// 后面的数值进行排查
while (cur.next && cur.next.val === repeat) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
};
# 链表的反复遍历
这类题的特点是：一定涉及反复遍历；同时，涉及相对复杂的链表操作，比如反转、指定位置的删除等等。
# 快慢指针-删除倒数第 n 个结点
快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩个指针。有一些更复杂的问题会涉及多指针（链表全部反转/局部反转）。
19. 删除链表的倒数第 N 个结点 (opens new window)
真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
# 链表的反转
206. 反转链表 (opens new window)（多指针法，prev、cur、next）
# 回文链表
解决方法：
- 将值复制到数组中后用双指针法（时间复杂度 O(n)，空间复杂度 O(n)）
var isPalindrome = function(head) {
if (!head) return true;
const array = [];
let cur = head;
while (cur) {
array.push(cur.val);
cur = cur.next;
}
let slow = 0;
let fast = array.length - 1;
while (slow <= fast) {
if (array[slow] !== array[fast]) {
return false;
} else {
slow++;
fast--;
}
}
return true;
};
把链表变成双向链表, 并从两端向中间比较
时间复杂度为 O(n), 因为要存储 prev 指针, 所以空间复杂度为 O(n)快慢指针 + 链表反转(难点：反转开始的点)
var isPalindrome = function(head) {
if (!head) return true;
let mid = getMidNode(head);
// 从中间节点的下一个节点断开
let tempStartNodes = reverseNodes(mid.next);
let left = head;
let right = tempStartNodes;
while (right) {
if (right.val !== left.val) {
return false;
}
right = right.next;
left = left.next;
}
// 还原链表
mid.next = tempStartNodes;
return true;
};
// 反转后面节点
const reverseNodes = function(head) {
let prev = null;
let cur = head;
while (cur) {
// 暂存
const temp = cur.next;
cur.next = prev;
// 相对下一个节点操作
prev = cur;
cur = temp;
}
// 返回最后节点
return prev;
};
// 快慢指针获取到中间节点
// 偶数情况下，会将对称前一个节点返回
// 奇数情况下，会讲中间节点返回
const getMidNode = function(head) {
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
# 旋转链表
思路：记给定链表的长度为 nn，注意到当向右移动的次数 k \geq nk≥n 时，我们仅需要向右移动 k \bmod nkmodn 次即可。因为每 nn 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n - 1) - (k \bmod n)(n−1)−(kmodn) 个节点（从 00 开始计数）。
这样，我们可以先将给定的链表连接成环，然后将指定位置断开。
# 链表成环
# 是否有环
- 可利用 map 哈希表来匹配 key 值，key 存引用；
- 借助快慢指针，原理是：慢指针一次一步快指针一次两步，前后赛跑总会有重合时，重合时即证明是环。
# 求入环点
假设入环之前的长度为 L, 入环之后快慢指针第一相遇时快指针比慢指针 🐢 多跑了 N 圈, 每一圈的长度为 C, 此时快指针 🐰 在环内离入环节点的距离为 C'（🐢 和 🐰 在此处第一次相遇）
此时慢指针 🐢 走过的距离为:L + C'
此时快指针 🐰 走过的距离为:L + C' + N * C
因为快指针 🐰 的速度是慢指针 🐢 的两倍, 所以有:2 * (L + C') = L + C' + N * C
即：L = N * C - C'
我们并不关心 N 是多少，假设 N =1，即存在 L = C - C'，
由此可知, 若此时有两个慢指针 🐢 同时分别从链表头结点和快慢指针第一次相遇的节点出发, 两者必然会在入环节点相遇。
← 👉 链表基础