HOT100-链表类题
HOT100系列-链表类型题
核心思想
例题
1、相交链表
题目描述：
给你两个单链表的头节点 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
**输出：**No intersection
**解释：**从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
解题思路：
- 首先找出那个链表长，那个链表短
- 长链表移动到和短链表相同长度的位置，然后比较节点是否相同
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode h1, ListNode h2) {
if(h1==null || h2==null){
return null;
}
//先判断那个链表场一点
ListNode a=h1;
ListNode b=h2;
int diff=0;
while(a.next!=null){
diff++;
a=a.next;
}
while(b.next!=null){
diff--;
b=b.next;
}
//若两个链表终点位置不同，则不相交
if(a!=b){
return null;
}
//a表示长链表，b表示锻炼表
//注意，现在的a,b都不在头结点上
if(diff>0){
a=h1;
b=h2;
}else{
a=h2;
b=h1;
}
//让长链表走到与短链表长度相同的位置
diff=Math.abs(diff);
while(diff>0){
a=a.next;
diff--;
}
while(a!=b){
a=a.next;
b=b.next;
}
return a;
}
}
2、反转链表
题目描述：
给你单链表的头节点 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
**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
代码如下：
/**
* 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) {
//注意下面两个记录的是翻转后的链表的pre和next
ListNode pre=null;
ListNode next=null;
while(head!=null){
//将原链表下一个节点保存
pre=head.next;
//开始逐步反转
head.next=next;
//head走到下一个需要翻转的节点，那么next移到当前head位置上(将会是下一个反转节点的next)
next=head;
head=pre;
}
return next;
}
}
3、回文链表
题目描述：
给你一个单链表的头节点 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.
* 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 boolean isPalindrome(ListNode head) {
//先找到整个链表中点的位置
//然后中点后面的节点反转
//然后，从两边向中间比对，判断是否为回文链表
//最后将链表复原
if(head==null || head.next==null){
return true;
}
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null && fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
//这个时候slow节点所在位置就是整个链表的中点位置
//将中点位置后面的链表节点进行反转
ListNode next=slow;
ListNode h2=slow.next;
slow.next=null;
ListNode pre=null;
while(h2!=null){
pre=h2.next;
h2.next=next;
next=h2;
h2=pre;
}
//拿到反转后的链表的头结点,原链表的头结点
ListNode h3=next;
ListNode h1=head;
//开始比较判断是否为回文链表
boolean flag=true;
while(h1!=null && h3!=null){
if(h1.val!=h3.val){
flag=false;
break;
}
h1=h1.next;
h3=h3.next;
}
//最后将链表复原
h2=next;
next=null;
pre=null;
while(h2!=null){
pre=h2.next;
h2.next=next;
next=h2;
h2=pre;
}
return flag;
}
}
4、环形链表
题目描述：
给你一个链表的头节点 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 <= 105pos为-1或者链表中的一个 有效索引 。
**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？
解题思路：
- 快慢指针
代码如下：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null){
return false;
}
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null && fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
5、环形链表Ⅱ
题目描述：
给定一个链表的头节点 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 <= 105pos的值为-1或者链表中的一个有效索引
**进阶：**你是否可以使用 O(1) 空间解决此题？
解题思路：
- 先定义快慢指针，快指针走2步，慢指针走一步，先找到快慢指针相遇的位置
- 找到后，head从头出发，慢指针仍然每次走1步，直到相遇，此时的位置就是环开始的位置
代码如下：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//先找到两者相遇的节点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
//相遇后
if (slow == fast) {
while(slow!=head){
slow=slow.next;
head=head.next;
}
return head;
}
}
return null;
}
}
6、合并两个有序链表
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 <= 100l1和l2均按 非递减顺序 排列
解题思路：
- 两个链表合并为一个，首先要判断谁是头结点
- 得到头结点后，得到两个列表下一次改判断的节点，开始判断
- 注意，不能用头结点直接进行next，最后是要返回头部的
代码如下：
class Solution {
public ListNode mergeTwoLists(ListNode h1, ListNode h2) {
if(h1==null || h2==null){
return h1==null?h2:h1;
}
//最终链表的头结点
ListNode head=h1.val<h2.val?h1:h2;
//两个链表的下一个改进行判断的元素
ListNode cur1=head.next;
ListNode cur2=head==h1?h2:h1;
ListNode pre=head;
while(cur1!=null && cur2!=null){
if(cur1.val<cur2.val){
pre.next=cur1;
cur1=cur1.next;
}else{
pre.next=cur2;
cur2=cur2.next;
}
pre=pre.next;
}
//不要忘记最后一个元素
pre.next=cur1==null?cur2:cur1;
return head;
}
}
7、两数相加
题目描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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- 题目数据保证列表表示的数字不含前导零
解题思路：
- 构造一个新的链表存放两个链表的加值
- 但是要注意，携带的进位，同时当最后两个链表都遍历完了后，若进位不为0，需要再在结果链表上构造新节点
代码如下
class Solution {
public ListNode addTwoNumbers(ListNode h1, ListNode h2) {
ListNode ans=null;
ListNode cur=null;
//进位
int carry=0;
for(int val,sum;h1!=null || h2!=null;h1=h1!=null?h1.next:null,h2=h2!=null?h2.next:null){
sum=(h1==null?0:h1.val)+(h2==null?0:h2.val)+carry;
val=sum%10;
carry=sum/10;
if(ans==null){
cur=new ListNode(val);
ans=cur;
}else{
cur.next=new ListNode(val);
cur=cur.next;
}
}
if(carry!=0){
cur.next=new ListNode(carry);
}
return ans;
}
}
8、删除链表的倒数第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 <= 300 <= Node.val <= 1001 <= n <= sz
**进阶：**你能尝试使用一趟扫描实现吗？
解题思路：
- 由于删除的元素可能在头位置，或者删除了直接为空，所以需要一个哨兵节点
- 查找链表的长度
- 找到删除节点的前一个节点的位置
- 删除倒数第n个节点
- 注意有可能删除的是头结点，所以头应该是哨兵的下一个元素
代码如下
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//由于删除的元素可能在头位置，或者删除了直接为空，所以需要一个哨兵节点
ListNode dumyhead=new ListNode(0,head);
//查找链表的长度
int size=0;
ListNode post=dumyhead;
while(post.next!=null){
post=post.next;
size++;
}
//找到删除节点的前一个节点的位置
ListNode pre=dumyhead;
for(int i=0;i<size-n;i++){
pre=pre.next;
}
//删除倒数第n个节点
pre.next=pre.next.next;
//注意有可能删除的是头结点，所以头应该是哨兵的下一个元素
return dumyhead.next;
}
}
9、两两交换链表中的节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
**输入：**head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
**输入：**head = []
输出：[]
示例 3：
**输入：**head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
解题思路：
代码如下：
class Solution {
public ListNode swapPairs(ListNode head) {
//利用哨兵节点，后续快速返回头部
ListNode dumyhead=new ListNode(0,head);
ListNode node0=dumyhead;
ListNode node1=head;
//开始交换
while(node1!=null && node1.next!=null){
//node 1和node2交换，node3为下一轮要交换的起始节点
ListNode node2=node1.next;
ListNode node3=node2.next;
//开始交换，node0表示要交换节点对的前一个节点
node0.next=node2;
node2.next=node1;
node1.next=node3;
//为下一组节点组交换做准备
node0=node1;
node1=node3;
}
return dumyhead.next;
}
}
10、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]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
解题思路：
- 查看是否有K个元素
- 找到下一组的K个元素的头尾节点
- 先将上一组尾节点指向下一组为节点
- 翻转当前组
- 记录当前组翻转后的尾节点
代码如下
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode start=head;
//查看是否有K个元素
ListNode end=teamEnd(k,start);
//链表没有K个元素
if(end==null){
return head;
}
//链表有K个元素
//第一组的K个元素翻转与其余组不同，第一组翻转后的头不用被指向，先处理
head=end;
//翻转从start到end的节点
reverse(start,end);
//记录上一组翻转的最后一个节点
ListNode lastTeamEnd=start;
//开始后续组的反转
while(lastTeamEnd.next!=null){
//下一组起点
start=lastTeamEnd.next;
//终点
end=teamEnd(k,start);
//接下来的元素不足K个
if(end==null){
return head;
}
//由于要翻转，先让上一组的最后节点指向下一组翻转后的头结点end
lastTeamEnd.next=end;
reverse(start,end);
//翻转完后，让上一组的最后节点变为翻转组后的最后节点，为下一组迭代做准备
lastTeamEnd=start;
}
return head;
}
//从start出发，查看后面是否有k个元素，返回从start出发的k个元素的末尾
public ListNode teamEnd(int k,ListNode start){
while(--k>0 && start!=null){
start=start.next;
}
return start;
}
//翻转start到end的节点
public void reverse(ListNode start,ListNode end){
//翻转组的下一个节点
end=end.next;
//剩余就是之前做过的联编翻转的思路
ListNode cur=start;
ListNode pre=null;
ListNode next=null;
while(cur!=end){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
//翻转后start来到最后，使其原本反转组的下一个节点连接起来
start.next=end;
}
}
11、随机链表的复制
题目描述：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
**输入：**head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
**输入：**head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
**输入：**head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000-104 <= Node.val <= 104Node.random为null或指向链表中的节点。
解题思路：
- 这个题真正的难点在于，我们照着原节点复制之后，对于其random，我们不知道对应的节点在那个位置，哪怕我们肯能已经复制出了这个节点
- 所以，为了能够快速找到，我们要在原链表的基础之上复制，借助原链表的对应关系来寻找
- 即
- 将所有的节点复制一份并插入其中，如1->2->3->4 变成 1->1’->2->2’->3->3’->4->4’
- 依照原本的节点的random指针为对应复制节点的random指针赋值
- 现在链表的复制节点的random指针已经依照原始链表对应，接下来就需要将原始链表还原并将复制节点提取出来组成结果链表
代码如下：
class Solution {
public static Node copyRandomList(Node head) {
if(head==null){
return null;
}
//将所有的节点复制一份并插入其中
//1->2->3->4 变成 1->1'->2->2'->3->3'->4->4'
Node cur=head;
Node next=null;
while (cur!=null){
next=cur.next;
Node copy=new Node(cur.val);
cur.next=copy;
copy.next=next;
cur=next;
}
//依照原本的节点的random指针为对应复制节点的random指针赋值
cur=head;
Node copy=null;
while (cur!=null){
copy=cur.next;
copy.random=cur.random!=null?cur.random.next:null;
if(cur.next.next==null){
break;
}
cur=cur.next.next;
}
//现在链表的复制节点的random指针已经依照原始链表对应，接下来就需要将原始链表还原并将复制节点提取出来组成结果链表
cur=head;
Node ans=cur.next;
while (cur!=null){
next=cur.next.next;
copy=cur.next;
copy.next=next!=null?next.next:null;
cur.next=next;
cur=next;
}
return ans;
}
}
12、排序链表
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
**输入：**head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
**输入：**head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
**输入：**head = []
输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解题思路：
- 归并排序的思想
- 这个题好难写，啊啊啊
代码如下
class Solution {
public static ListNode sortList(ListNode head) {
//统计链表长度
int n=0;
ListNode cur=head;
while (cur!=null){
n++;
cur=cur.next;
}
//l1,r1第一组第一部分左右节点，l2,r2第一组链表第二部分左右节点,next 下一组的开头,lastTeamEnd 上一组的结尾
ListNode l1,r1,l2,r2,next,lastTeamEnd;
for(int step=1;step<n;step<<=1){
//找到第一组链表的头尾（最左右节点）,第一组十分特殊，决定了当前链表的头尾节点所以要单独拿出来
l1 = head;
r1=findEnd(l1,step);
l2=r1.next;
r2=findEnd(l2,step);
//保存整个链表剩余节点
next=r2.next;
//将待排序的取出来的一组链表与其他组待排序链表截断
r1.next=null;
r2.next=null;
//利用归并排序将待排序的两个链表合并
merge(l1,r1,l2,r2);
head=start;
lastTeamEnd=end;
//注意归并排序迭代时是每一次当步长较小时，一条链表会分成多个排序小组
while (next!=null){
l1=next;
r1=findEnd(l1,step);
l2=r1.next;
//若剩余不足，已经到底
if(l2==null){
lastTeamEnd.next=l1;
break;
}
r2=findEnd(l2,step);
//保存整个链表剩余节点
next=r2.next;
//将待排序的取出来的一组链表与其他组待排序链表截断
r1.next=null;
r2.next=null;
//利用归并排序将待排序的两个链表合并
merge(l1,r1,l2,r2);
//将每组排序后的链表连接起来
lastTeamEnd.next=start;
lastTeamEnd=end;
}
}
return head;
}
private static ListNode findEnd(ListNode s, int k) {
while (s.next!=null && --k!=0){
s=s.next;
}
return s;
}
public static ListNode start;
public static ListNode end;
private static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
ListNode pre;
//第一次比较很重要，找到这一组排序链表的头
if(l1.val<=l2.val){
start=l1;
pre=l1;
l1=l1.next;
}else {
start=l2;
pre=l2;
l2=l2.next;
}
while (l1!=null && l2!=null){
if(l1.val<=l2.val){
pre.next=l1;
pre=l1;
l1=l1.next;
}else {
pre.next=l2;
pre=l2;
l2=l2.next;
}
}
if (l1!=null){
pre.next=l1;
end=r1;
} else {
pre.next=l2;
end=r2;
}
}
}
13、合并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 = [[]]
输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
解题思路：
- 有两种思路
- 思路一：将所有节点放于小根堆中，每次从小根堆取
- 思路二：分支的思想，参考合并两个有序链表，每次将每两个链表进行合并
代码如下
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//统计有多少链表
int n=lists.length;
if(n==0){
return null;
}
//每两个链表合并，知道合并为1个链表
for(int step=1;step<n;step<<=1){
//注意i+=step*2
for(int i=0;i<n-step;i+=step*2){
lists[i]=merge(lists[i],lists[i+step]);
}
}
return lists[0];
}
//合并两个有序链表
public ListNode merge(ListNode h1,ListNode h2){
//哨兵节点
ListNode dumyhead=new ListNode();
ListNode cur=dumyhead;
while(h1!=null && h2!=null){
if(h1.val<=h2.val){
cur.next=h1;
h1=h1.next;
}else{
cur.next=h2;
h2=h2.next;
}
cur=cur.next;
}
cur.next=h1==null?h2:h1;
return dumyhead.next;
}
}
14、LRU 缓存
题目描述：
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
解题思路：
- 就是一个LRU的实现
- 首先定义双向链表节点
- 然后定义双向链表
- 头尾节点
- 添加新节点的方法
- 节点移动到尾部的方法
- 删除头结点并返回头结点的方法
- 定义快速找到对应节点的hashmap
- 定义LRU容量
class LRUCache {
//定义双向链表Node节点
class DoubleNode {
public int key;
public int value;
DoubleNode next;
DoubleNode last;
public DoubleNode(int key, int value) {
this.key = key;
this.value = value;
}
}
//定义双向链表结构
class DoubleNodeList {
DoubleNode head;
DoubleNode tail;
public DoubleNodeList() {
head = null;
tail = null;
}
//添加节点
public void addNode(DoubleNode newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.last = tail;
tail = newNode;
}
}
//将节点移到尾节点上面
public void moveNodeToTail(DoubleNode node) {
if (tail == node) {
return;
}
if (head == node) {
head = head.next;
head.last = null;
} else {
node.last.next = node.next;
node.next.last = node.last;
}
tail.next = node;
node.last = tail;
node.next = null;
tail = node;
}
//移除头结点
public DoubleNode removeHead() {
if (head == null) {
return null;
}
DoubleNode ans = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = ans.next;
ans.next = null;
head.last = null;
}
return ans;
}
}
//定义hashMap
private HashMap<Integer, DoubleNode> keyNodeMap;
private DoubleNodeList nodeList;
private final int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
nodeList = new DoubleNodeList();
keyNodeMap = new HashMap<>();
}
public int get(int key) {
if (keyNodeMap.containsKey(key)) {
DoubleNode ans = keyNodeMap.get(key);
nodeList.moveNodeToTail(ans);
return ans.value;
}
return -1;
}
public void put(int key, int value) {
if (keyNodeMap.containsKey(key)) {
DoubleNode node = keyNodeMap.get(key);
node.value = value;
nodeList.moveNodeToTail(node);
} else {
if (keyNodeMap.size() >= capacity) {
keyNodeMap.remove(nodeList.removeHead().key);
}
DoubleNode node = new DoubleNode(key, value);
keyNodeMap.put(key, node);
nodeList.addNode(node);
}
}
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
22
0- 0
已为社区贡献2条内容
所有评论(0)