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;
    }
}

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