LeetCode23合并k个有序链表
复习两个有序链表合并
递归
private ListNode merge2Lists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = merge2Lists(l1.next, l2);
return l1;
}
l2.next = merge2Lists(l1, l2.next);
return l2;
}
迭代
private ListNode merge2Lists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 == null? l2: l1;
return dummyHead.next;
}
方法一：顺序合并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0){
return null;
}
ListNode l1 = lists[0];
for(int i=1;i<lists.length;i++){
l1 = merge(l1,lists[i]);
}
return l1;
}
public ListNode merge(ListNode l1, ListNode l2){
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
if(l1.val>l2.val){
l2.next = merge(l1,l2.next);
return l2;
}else{
l1.next = merge(l1.next,l2);
return l1;
}
}
}
方法二：分治
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0){
return null;
}
int i = 0;
int j = lists.length-1;
ListNode l = unmerge(lists,i,j);
return l;
}
public ListNode unmerge(ListNode[] lists,int i,int j){
if(i==j){
return lists[i];
}else{
int mid = (i+j)/2;
ListNode l1 = unmerge(lists,i,mid);
ListNode l2 = unmerge(lists,mid+1,j);
ListNode l = merge(l1,l2);
return l;
}
}
public ListNode merge(ListNode l1, ListNode l2){
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
if(l1.val>l2.val){
l2.next = merge(l1,l2.next);
return l2;
}else{
l1.next = merge(l1.next,l2);
return l1;
}
}
}
方法三：K指针
k个指针指向k条链表，比较出最小值，依次添加至合并后的链表；
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (true) {
ListNode minNode = null;
int minPointer = -1;
for (int i = 0; i < k; i++) {
if (lists[i] == null) {
continue;
}
if (minNode == null || lists[i].val < minNode.val) {
minNode = lists[i];
minPointer = i;
}
}
if (minPointer == -1) {
break;
}
tail.next = minNode;
tail = tail.next;
lists[minPointer] = lists[minPointer].next;
}
return dummyHead.next;
}
}
方法四：优先队列，对于方法三的优化。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
for (ListNode node: lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (!pq.isEmpty()) {
ListNode minNode = pq.poll();
tail.next = minNode;
tail = minNode;
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummyHead.next;
}
}
Processed:
0.015, SQL:
8
