合并两个排序链表
- 模拟维护一个合并链表，每次添加两个排序链表中较小val的节点即可
模拟代码
public ListNode mergeTwo(ListNode a, ListNode b) {
if(a == null) return b;
if(b == null) return a;
ListNode ans = new ListNode(0);
ListNode ans0 = ans;
while(a != null && b != null) {
if(a.val <= b.val) {
ans.next = new ListNode(a.val, null);
a = a.next;
} else {
ans.next = new ListNode(b.val, null);
b = b.next;
}
ans = ans.next;
}
if(a != null) {
ans.next = a;
} else {
ans.next = b;
}
return ans0.next;
}
合并K个排序链表
顺序合并
- 两两合并链表即可
顺序合并代码
/**
* 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 mergeKLists(ListNode[] lists) {
int len = lists.length;
ListNode ans = null;
for(int i = 0; i < len; ++ i ) {
ans = mergeTwo(ans, lists[i]);
}
return ans;
}
public ListNode mergeTwo(ListNode a, ListNode b) {
if(a == null) return b;
if(b == null) return a;
ListNode ans = new ListNode(0);
ListNode ans0 = ans;
while(a != null && b != null) {
if(a.val <= b.val) {
ans.next = new ListNode(a.val, null);
a = a.next;
} else {
ans.next = new ListNode(b.val, null);
b = b.next;
}
ans = ans.next;
}
if(a != null) {
ans.next = a;
} else {
ans.next = b;
}
return ans0.next;
}
}
分治合并
- 基于两两合并，再分治思想递归合并链表数组
分治合并代码
/**
* 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 mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if(l == r) return lists[l];
// 边界值：lists.length = 0会出现 l>r
if(l > r) return null;
int mid = l + ((r - l) >> 1);
return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwo(ListNode a, ListNode b) {
if(a == null) return b;
if(b == null) return a;
ListNode ans = new ListNode(0);
ListNode ans0 = ans;
while(a != null && b != null) {
if(a.val <= b.val) {
ans.next = new ListNode(a.val, null);
a = a.next;
} else {
ans.next = new ListNode(b.val, null);
b = b.next;
}
ans = ans.next;
}
if(a != null) {
ans.next = a;
} else {
ans.next = b;
}
return ans0.next;
}
}
使用优先队列合并
使用优先队列维护两个排序链表中的值，然后按照优先队列中升序元素构造新的合并链表即可
使用优先队列合并代码
/**
* 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 mergeKLists(ListNode[] lists) {
int len = lists.length;
Queue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < len; ++ i ) {
while(lists[i] != null) {
pq.offer(lists[i].val);
lists[i] = lists[i].next;
}
}
ListNode head, tail;
head = tail = null;
while(!pq.isEmpty()) {
int val = pq.poll();
if(head == null) head = tail = new ListNode(val, null);
else {
tail.next = new ListNode(val, null);
tail = tail.next;
}
}
return head;
}
}