LeetCode 23:Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

 

又是链表,不过这次输入变成了一个链表类型的数组,最无脑的方法应该还是遍历数组,然后遍历每一个链表,将所有元素添加到一个ArrayList里,排序后,存放到链表里返回

写起来很简单,但是时间复杂度很高,应该会超时

Java源码

package com.maoxiaomeng;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/


class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}

public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
List<Integer> myList = new ArrayList<Integer>();
for (ListNode list : lists) {
while (list != null) {
myList.add(list.val);
list = list.next;
}
}
Collections.sort(myList);
ListNode l = new ListNode(myList.get(0));
ListNode head = l;
int i = 1;
while (i < myList.size()) {
l.next = new ListNode(myList.get(i));
l = l.next;
i++;
}
return head;
}
}

提交之后果然超时了

参考了Solution类似归并排序的解法

package com.maoxiaomeng;


/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/


class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}

public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (lists == null || len == 0) {
return null;
} else if (len == 1) {
return lists[0];
}

while (len > 1) {
int middle = (len + 1) / 2;
for (int i = 0; i < len / 2; i++) {
lists[i] = merge(lists[i], lists[i + middle]);
}
len = middle;
}
return lists[0];
}

public ListNode merge(ListNode left, ListNode right) {
if (left == null) {
return right;
}
if (right == null) {
return left;
}
ListNode head = new ListNode(0);
ListNode current = head;
while (left != null && right != null) {
if (left.val < right.val) {
current.next = left;
left = left.next;
} else {
current.next = right;
right = right.next;
}
current = current.next;
}
if (left != null) {
current.next = left;
} else {
current.next = right;
}
return head.next;
}
}

还看了一种通过优先队列来解决的

发表回复