# 算法系列--链表刷题(二)（下）

https://developer.aliyun.com/article/1480808?spm=a2c6h.13148508.setting.14.5f4e4f0e08yH7p

## 4.合并 K 个升序链表（hard）

https://leetcode.cn/problems/merge-k-sorted-lists/description/

/**
* 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 mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((o1,o2) ->o1.val - o2.val);
ListNode ret = new ListNode(0);
while(!heap.isEmpty()) {
ListNode tmp = heap.poll();
if(tmp.next != null) heap.offer(tmp.next);// 注意下一个节点可能为空
}
return ret.next;
}
}

/**
* 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 mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
// 采用归并的思想解决
return merge(lists,0,lists.length-1);
}
public ListNode merge(ListNode[] lists,int left,int right) {
// 递归出口
if(left >= right) return lists[left];
int mid = (left + right) /2;
ListNode l1 = merge(lists,left,mid);
ListNode l2 = merge(lists,mid + 1,right);
return mergeTwoLists(l1,l2);
}
// 合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 递归
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else {
list2.next = mergeTwoLists(list2.next,list1);
return list2;
}
}
}

## 5.K个⼀组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

1. 求出要反转多少个长度为K的链表–n
2. 翻转n次即可

/**
* 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) {
// 求需要翻转的组数n
int cnt = 0;
while(tmp != null) {
cnt++;
tmp = tmp.next;
}
int n = cnt / k;
// 开始进行翻转
ListNode ret = new ListNode(0);
for(int i = 0; i < n; i++) {
ListNode prev = cur;// 保存当前翻转链表的头结点
for(int j = 0; j < k; j++) {
ListNode curnext = cur.next;
cur = curnext;
}
}
return ret.next;
}
}`

|
2天前
|

4 0
|
2天前
|

10 0
|
2天前
|

5 0
|
2天前
|

12 0
|
2天前
|

12 0
|
2天前
|

8 0
|
2天前
|

9 0
|
2天前
|

7 0
|
7天前
|

9 2
|
7天前
|

12 0