链表相关
21. 合并两个有序链表
问题
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = []
输出：[]示例 3：
输入：l1 = [], l2 = [0]
输出：[0]提示
双指针轻松拿下。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
ListNode head = new ListNode(-1);
ListNode dummyHead = head;
while(list1 != null && list2 != null){
if(list1.val > list2.val) {
dummyHead.next = list2;
list2 = list2.next;
}else if (list1.val <= list2.val) {
dummyHead.next = list1;
list1 = list1.next;
}
dummyHead = dummyHead.next;
}
if(list1 == null) dummyHead.next = list2;
if(list2 == null) dummyHead.next = list1;
return head.next;
}
}23. 合并 K 个升序链表
问题
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]提示
利用优先级队列（小根堆）的特性，优先级队列的头节点就是当前链表的最小节点，我们总能拿到每个链表的最小节点，每取出一个最小节点，就会有下一个最小节点当做头节点。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
import java.util.*;
class Solution {
/**
由于我们总要得到k个链表中的最小的一个节点,
有这么一个数据结构就可以实现我们的需求
优先级队列
使用优先级队列总是得到最小的节点, 然后将这个节点的下一个节点再次放入队列
*/
public ListNode mergeKLists(ListNode[] lists) {
// 如果都为空直接返回null
if(lists.length == 0) return null;
// 创建虚拟头结点和优先级队列
ListNode dummyHead = new ListNode(-1);
ListNode curr = dummyHead;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((a,b)->a.val-b.val);
//先将k个链表的头节点放入优先级队列
for(ListNode node : lists) {
if(node == null) continue;
queue.add(node);
}
// 循环条件只要队列里还有节点
while(queue.size()>0) {
// 取出最小节点
ListNode temp = queue.poll();
curr.next = temp;
curr = curr.next;
// 如果最小节点的next不为空就将next放入队列
if(temp.next != null){
queue.add(temp.next);
}
}
// 返回虚拟头节点的next
return dummyHead.next;
}
}86. 分隔链表
问题
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]示例 2：
输入：head = [2,1], x = 2
输出：[1,2]提示
双指针分别去拿小于x的和大于等于x的节点，然后合并两个链表，要注意的是，拿到节点后，要将节点和原链表断开，否则就成了死链。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
直接双指针轻松秒杀, 但是有些细节需要注意
*/
public ListNode partition(ListNode head, int x) {
// 创建两个虚拟头节点, 一个用于返回, 一个用于连接
ListNode dummyHead1 = new ListNode(-1);
ListNode dummyHead2 = new ListNode(-1);
// 创建两个操作节点
ListNode p1 = dummyHead1;
ListNode p2 = dummyHead2;
// 遍历head
while(head!=null) {
if(head.val < x) {
p1.next = head;
p1 = p1.next;
// 这里记得操作完将原链表断开否则容易出现死链
head = head.next;
p1.next = null;
} else {
p2.next = head;
p2 = p2.next;
// 同上
head = head.next;
p2.next = null;
}
}
// 连接两个链表
p1.next = dummyHead2.next;
// 返回头节点
return dummyHead1.next;
}
}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]提示
快慢指针，快指针先走n步，然后快慢一起走，快指针走到最后一个节点，慢指针就刚好在要删除的节点的前驱节点上。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
快慢指针, 让快指针先走 n 步, 然后两个指针一块走
快指针走到最后一个, 慢指针就得到了要删除节点的前驱节点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建快慢指针和要返回的节点头
ListNode res = head;
ListNode fast = head;
ListNode slow = head;
// 快指针先走
while(n-->0) {
fast = fast.next;
}
// 这里判断一下如果fast为null, 说明要删除的节点是第一个
if(fast == null) {
return res.next;
}
// 快慢指针一块走
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 此时slow为需要删除的前驱节点, 直接删除
slow.next = slow.next.next;
// 返回头节点
return res;
}
}876. 链表的中间结点
问题
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。提示
依旧是快慢指针，快指针一次走两步，慢指针一次走一步，需要注意一下双数节点的链表的返回要求。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
依旧是快慢指针, 快指针一次走两步, 慢指针一次走一步
快指针走到头, 慢指针就到中间了
*/
public ListNode middleNode(ListNode head) {
// 创建快慢指针
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next !=null) {
fast = fast.next.next;
slow = slow.next;
}
// 如果fast刚好走到最后一个节点, 说明此时slow就是中间节点
if(fast.next == null) return slow;
// 如果fast走到倒数第一个节点, 那么根据题目要求我们需要返回靠右的节点
return slow.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
解释：链表中没有环。提示
快指针一次走两步，慢指针一次走一步，只要有环，我们早晚会相遇。
示例
java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
依旧快慢指针, 快指针一次走两步, 慢指针一次走一步, 如果相遇就是有环
*/
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
}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
解释：链表中没有环。提示
还是先用上面的思路看有没有环，有环的话，将快指针从新放回头节点，快慢指针一起一步一步走，相遇的时候就是环的起点，这是一个数学问题🤔
示例
java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
这里涉及到一个数学问题，当快慢指针在换中相遇后，
把快指针放回头节点，然后和慢指针一起一步一步走，
再次相遇时就是环的起点。
*/
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode fast = head, slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
fast = head;
while(fast!=slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}160. 相交链表
问题
给你两个单链表的头节点 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
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。提示
这是一个数学问题A+B=B+A，两个指针同时往下走，走到尾巴就换到另一个链表的头开始走，如果相交，两个指针就会在相交点相遇，如果不相交，则会同时走到尾。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
这里是一个数学问题, A+B=B+A,
两个指针走到尾巴时指向另一个链表的头
会在交点处相遇, 如果没有交点, 则会在换头后同时到达尾巴
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 如果其中一个链表为null, 说明必没有交点
if(headA == null || headB == null) return null;
ListNode p = headA;
ListNode q = headB;
while(p != q) {
p = p == null ? headB : p.next;
q = q == null ? headA : q.next;
}
// 由于我们了解的特性, 循环完之后无论是有无节点, 其中任意一个节点都是我们要返回的
return p;
}
}206. 反转链表
问题
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]提示
双指针，不断从头获取一个节点接到临时节点的下一个节点上，最后临时节点下一个节点就是反转后的链表的头节点。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
如果对指针熟悉的话, 双指针即可轻松秒杀
*/
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while(curr != null) {
// 先用临时节点保存next
ListNode temp = curr.next;
// 当前节点接上已反转的节点
curr.next = prev;
// 把新接好反转链表拿到
prev = curr;
// curr到下一个
curr = temp;
}
return prev;
}
}92. 反转链表 II
问题
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]提示
先拿到前驱节点，然后将中间部分反转，最后组合起来，组合的时候比较考验对链表的理解，可以根据示例代码动手画图看一下。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 定义虚拟头节点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
// 操作此节点拿到反转部分的前驱节点
ListNode superior = dummyHead;
for(int i = 1; i < left; i++) {
superior = superior.next;
}
// 反转链表的操作
ListNode curr = superior.next;
ListNode prev = null;
for(; left <= right; left++) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// 组合链表
/**
这里看superior.next其实就是反转部分的尾巴,
superior.next.next = curr 相当于是将反转后的部分和后驱节点连接,
prev则是反转部分链表的头节点,
superior.next = prev 就是将前驱节点和反转部分链接
*/
superior.next.next = curr;
superior.next = prev;
return dummyHead.next;
}
}25. K 个一组翻转链表
问题
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]提示
这里我们用递归的思想，把链表分为k个一组，去反转然后链接，不断用上一组链表的头节点也就是翻转后的尾节点连接下一组翻转后返回的头节点。链表的反转参考上一题。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
这道题我们用到了分组递归的思想, 每次递归连接下次递归的新链头
*/
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null) return head;
ListNode a = head, b = head;
for(int i = 0; i < k; i++){
// 这里考虑到最后不满k个, 所以不做反转, 并且退出递归
if(b == null) return head;
b = b.next;
}
// 得到新链表头
ListNode newHead = reverse(a, b);
// 让原来的链表头, 也就是反转后的尾巴去连接下一组的链表头
head.next = reverseKGroup(b, k);
// 返回新的链表
return newHead;
}
/**
这里就是将[a,b)左闭右开区间内的链表进行反转, 并且返回反转后的链表头
至于为什么是左闭右开而不是左右都闭合, 主要是考虑到占用内存的大小,
如果是左右闭区间, 我们还要在上面单独拿一个节点来存放下次递归的头,
如果是左闭右开, b就是我们下次递归的链表头, 并且在reverse中不会发生变化
*/
public ListNode reverse(ListNode a, ListNode b) {
ListNode curr = a;
ListNode prev = null;
while(curr != b) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}61. 旋转链表
问题
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]提示
链表的旋转次数与链表的实际深度有关系，我们真正需要旋转的次数是（旋转次数k%链表深度deep），而这道题的旋转其实就是将链表尾节点移到最前面作为头节点，所以我们可以直接倒数k%deep个节点前置即可。
示例
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// 对以下不需要旋转的情况直接返回
if (head == null || k == 0 || head.next == null) {
return head;
}
// 找到链表的最大深度和链表的最后一个节点
ListNode temp = head;
int deep = 1;
while (temp.next != null) {
temp = temp.next;
deep++;
}
/**
* 当k<deep时，需要将链表旋转k次，就是将倒数k个节点前置
* 也就是将deep-k节点与后面的节点前置
* 当k>deep时，能整除的部分为无效旋转，
* 只需要转转k%deep次即可
*/
// 得到需要将第n个节点放在表头
int n = deep - k % deep;
if (n == deep) { // 不需要旋转
return head;
}
// 将链表置为环形链表
temp.next = head;
// 找到第n个节点的前一个节点
while (n > 0) {
temp = temp.next;
n--;
}
// 拿到第n个节点
ListNode res = temp.next;
// 断开环形链表
temp.next = null;
// 返回新的链表头
return res;
}
}