链表的遍历
方法一：
function traverse (head) {while (head) {console.log(head.val)head = head.next}}
方法二：
function traverse(head) {
if (!head) return null
// 顺序遍历
console.log(head.val)
traverse(head.next)
// 倒序遍历
//console.log(head.val)
}
翻转链表
方法一：迭代
function reverse(head) {
let pre = null
let cur = head
while (cur) {
const next = cur.next
cur.next = pre
pre = cur
cur = next
}
return pre
}
方法二：递归
function reverse(head) {
if (!head || !head.next) return head
const last = reverse(head.next)
head.next.next = head
head.next = null
return last
}
合并两个有序链表-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 均按 非递减顺序 排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
var mergeTwoLists = function (list1, list2) {
let head = new ListNode();
let cur = head;
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
}else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 ? list1 : list2;
return head.next;
};
环形链表-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)（即，常量）内存解决此问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：
遍历链表的时候每遍历过一个元素后就给当前元素设置一个标记位 head.flag = true，如果链表遍历完都没有碰到 flag 为 true 的元素，则说明链表没有环，如果遍历到某个元素，它的 flag 为 true ，这说明链表有环。
var hasCycle = function (head) {
// 链表为空或者只有一个元素则，则说明没有环，返回false
if (!head || !head.next) return false;
// 遍历链表
while (head) {
head = head.next;
// 当前链表元素的 flag 为真，则说明遍历到了之前的元素，进而证明链表有环，返回 true
if (head.flag) return true;
// 给当前遍历的链表元素设置 flag 标记，如果再次遍历到，这说明链表有环
head.flag = true;
}
// 遍历完链表后，如果没有找到 flag 为 true 的链表，则说明链表没有环，返回 false
return false;
};
方法二：
使用快慢指针，快指针走两步，慢指针走一步，如果快指针最后指向了空，则表示链表没环；如果快慢指针最后相遇则说明链表有环。
var hasCycle = function(head) {
// 定义快慢指针
let slow = head, fast = head;
// 快指针有值，遍历链表
while (fast && fast.next) {
// 快指针走两步
fast = fast.next.next;
// 慢指针走一步
slow = slow.next;
// 快慢指针相遇表示链表有环返回 true
if (slow === fast) {
return true;
}
}
// 如果快指针最后指向了空，则表示链表没环返回 false
return false;
};
if(head ===null) return false
let pre = head, next = head.next;
while(pre !=next && next && next.next){
pre = pre.next
next = next.next.next
}
return pre === next
环形链表II-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 <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
通过前面的学习，可能有的朋友说那我们使用前面环形链表讲的的方法一不就行了吗，但是这个题目要求不能修改链表。那使用方法二呢？也是不行的，上题讲的 slow 和 fast 两个指针相撞时只能说明链表有环，但并没法说明它们相撞的点就是链表成环的交点。如：
从上图可以看出第一次两个交点相交是在节点 -4 的位置相交的，并不是入环的第一个交点。那我们应该怎么办呢？
var detectCycle = function(head) {
// 定义快慢指针
let fast = head, slow = head;
// 遍历链表
while (fast && fast.next) {
// 快指针前进两步
fast = fast.next.next;
// 慢指针前进一步
slow = slow.next;
// 快慢指针相撞说明链表成环，跳出循环
if (fast == slow) break;
}
// 此时如果fast指针为空或者fast.next 为空，则表明链表没有环，返回 null
if (!fast || !fast.next) return null;
// 将慢指针指向链表开头
slow = head;
// 当快慢指针没有相撞时遍历链表
while (slow != fast) {
// 慢指针逐步前进
slow = slow.next;
// 快指针逐步前进
fast = fast.next;
}
// 当快慢指针相同时慢指针或者快指针指向的就是链表入环的起始点，返回快慢指针指向的节点即可
return slow;
};
重排链表-143
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
- 快慢指针找中点
- 拆分成两个链表
- 遍历两个链表，将后面的链表中的元素间隔插入到前面链表中
```javascript
const head = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
} } } }val: 4, next: { val: 5, next: { val: 6, next: { val: 7, next: { val: 8, next: { val: 9, next: { val: 10, next: { val: 11, next: { val: 12, next: { val: 13, next: { val: 14, next: { val: 15, next: null } } } } } } } } } } }
// 找中点 function getMidNode(head) { if (!head || !head.next) return head
let slow = head, fast = head
while (fast && fast.next) { slow = slow.next fast = fast.next.next }
const res = slow.next slow.next = null return res }
// 翻转链表 function reverse(head) { if (!head || !head.next) return head
let pre = null, cur = head
while (cur) { const next = cur.next cur.next = pre pre = cur cur = next } return pre }
var reorderList = (head) => { if (!head || !head.next) return head
const reverseNode = reverse(getMidNode(head)) let p1 = head, p2 = reverseNode
while (p2) { let n1 = p1.next let n2 = p2.next
p1.next = p2
p2.next = n1
p1 = n1
p2 = n2
} }
reorderList(head)
console.log(JSON.stringify(head))
<a name="AgEhD"></a>
# 相交链表-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 个节点。 示例 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 输出：null 解释：从各自的表头开始算起，链表 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) 内存的解决方案？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：<br />如果两个链表的长度是相等的，那么这个题就很简单了。定义两个指针同时遍历两个链表，如果相交的话，两个指针的对撞的节点必然是同一个，这个节点就是交点；如果两个链表不相交，遍历完两个链表，两个指针必然都指向 null。
但是如果两个链表长度不相同，上面这样做就行不行了，但是我们可以想办法等他们长度相等的时候再开始同时遍历两个链表。
我们可以先得到两个链表的长度，计算出它们长度的差值，先让相对较长的那个链表的指针先走它们长度差值步，这样两个指针就对齐了，然后再按照上面的解法就可以得到最终答案了。<br /><br />代码如下：
```javascript
var getIntersectionNode = function(headA, headB) {
let lenA = 0, lenB = 0, p1 = headA, p2 = headB;
while (headA) {
lenA++;
headA = headA.next;
}
while (headB) {
lenB++;
headB = headB.next;
}
let diff = Math.abs(lenA - lenB);
let isA = lenA - lenB > 0 ? true : false;
while(diff) {
if (isA) {
p1 = p1.next;
}else {
p2 = p2.next;
}
diff--;
}
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
};
方法二：
假设两个链表相交，第一个指针遍历完第一个链表，然后遍历第二个链表；第二个指针遍历完第二个链表，然后遍历第一个链表，当两个指针相撞时，相撞的这个节点就是交点。
var getIntersectionNode = function(headA, headB) {
let p1 = headA, p2 = headB;
while (p1 != p2) {
if (p1) p1 = p1.next;
else p1 = headB;
if (p2) p2 = p2.next;
else p2 = headA;
}
return p1;
};
链表的中间节点-876
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var middleNode = function(head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
删除链表的倒数第 N 个结点-19
给你一个链表，删除链表的倒数第 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
进阶：你能尝试使用一趟扫描实现吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在看是做这道题之前，我们先做一个小题：返回链表中倒数第 N 个节点。
const head = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 4,
next: {
val: 5,
next: null
}
}
}
}
};
function findFromEnd(head, k) {
let fast = head, slow = head;
while (k && fast) {
fast = fast.next;
k--;
}
while (fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
console.log(findFromEnd(head, 2));
下面我们开始来解题：
var removeNthFromEnd = function (head, n) {
if (!head) return head;
let dummy = new ListNode();
dummy.next = head;
let fast = dummy;
let slow = dummy;
while (n) {
fast = fast.next;
n--;
}
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
};
链表中倒数第k个节点-剑指 Offer 22
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
删除排序链表中的重复节点-83
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var deleteDuplicates = function(head) {
if (!head) return null;
let cur = head;
while (cur && cur.next) {
if (cur.val == cur.next.val) cur.next = cur.next.next;
cur = cur.next;
}
return head;
};
删除排序链表中的重复节点II-82
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var deleteDuplicates = function (head) {
if (!head || !head.next) return head;
let dummy = new ListNode();
dummy.next = head;
let cur = dummy;
while (cur.next && cur.next.next) {
if (cur.next.val == cur.next.next.val) {
let val = cur.next.val;
while (cur.next && cur.next.val == val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
};
8. 旋转链表-61
9. 两两交换链表中的节点-24
10.反转链表II-92
11. 快乐数-202x
13. K个一组翻转链表-25x
14. 移除链表元素-203
15. 两数相加-3
16. 两两交换链表中的节点-24
17. 删除链表的节点-面试题-18
18. 反转链表-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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var reverseList = function (head) {
let pre = null;
let cur = head;
while (cur != null) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};
方法二：递归
var reverseList = function (head) {
if (head == null || head.next == null) return head;
let node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
};
19. 合并k个升序链表-23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：暴力解法
- 遍历 lists ，得到每个链表，然后再遍历每一个链表，将遍历到的链表的值存入一个数组
- 对存放链表值的数组进行排序
- 把排序后的数组转为一个新的链表并返回
方法二：var mergeKLists = function (lists) { const head = new ListNode(); let cur = head; let res = []; lists.forEach(list => { while (list) { res.push(list.val); list = list.next; } }); res = res.sort((a, b) => (a - b)); res.forEach(item => { let node = new ListNode(item); cur.next = node; cur = node; }); return head.next; };回文链表-234
``` 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true 示例 2：
输入：head = [1,2] 输出：false
提示：
链表中节点数目在范围[1, 105] 内 0 <= Node.val <= 9
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：<br />遍历链表将链表中的元素存入数组，然后使用头尾指针向中间遍历这个数组，如果 arr [i] !==arr[j] 说明不是回文链表返回 false。
```javascript
var isPalindrome = function(head) {
if (!head) return false;
const res = [];
let cur = head;
while (cur) {
res.push(cur.val)
cur = cur.next
}
let i = 0, j = res.length - 1;
while (i < j) {
if (res[i] !== res[j]) return false;
i++
j--
}
return true
};
方法二：模拟双指针
链表可以正序遍历也可以倒序遍历，我们可以同时进行，一个指针从头开始遍历链表，一个指针从尾开始遍历指针，每次遍历对比头尾两个指针的值是否相等，如果不等，说明这个链表不具有回文性返回 false。
let left = null
function isPalindrome(head) {
left = head
return traverse(head)
}
function traverse(right) {
// right 为空返回真，之所以返回真是为了可以比较数据
if (!right) return true
// res 用来承接每轮对比的结果
let res = traverse(right.next)
// 当某轮对比中 res 为 false 后，就不再对比链表的值
res = res && (right.val === left.val)
// 调整 left 的位置
left = left.next
// 返回对比结果
return res
}
let left = null
function isPalindrome(head) {
left = head
return traverse(head)
}
function traverse(right) {
if (!right) return true
let res = traverse(right.next)
if (!res) return false
res = right.val === left.val
left = left.next
return res
}
优化：
function isPalindrome(head) {
// 快慢指针用于寻找链表中点
let fast = head
let slow = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
//
if (fast) slow = slow.next
let left = head
// 从链表中点翻转链表
let right = reverse(slow)
// 遍历链表，这里遍历的条件是翻转后的链表有值，如果用 left 的话就要把整个链表遍历完，没必要
while (right) {
// 如果左右指针指向的值不相等，则说明链表不回文，直接返回 false
if (right.val !== left.val) return false
// 更新左右指针
left = left.next
right = right.next
}
// 返回结果
return true
}
function reverse(head) {
let pre = null
let cur = head
while (cur) {
const next = cur.next
cur.next = pre
pre = cur
cur = next
}
return pre
}
若有收获，就点个赞吧
0 人点赞
