一、题目内容

二、题解

解法1：

思路

链表拼接+链表排序
要求复杂度 nlogn，所以归并排序

代码

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null||lists.isEmpty()){
            return null;
        }
        return sortListNode(mergeList(lists));
    }
    private ListNode mergeList(ArrayList<ListNode> lists){
        ListNode head = lists.get(0);
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for(int i = 1;i<lists.size();i++){
            ListNode node = lists.get(i);
            while(head.next!=null){
                head = head.next;
            }
            head.next = node;
            while(head.next!=null){
                head = head.next;
            }
        }
        return dummy.next;
    }
    private ListNode sortListNode(ListNode head){
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode left = sortListNode(head);
        ListNode right = sortListNode(next);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}