LeetCode - Hard - 23. Merge k Sorted Lists-蒲公英云

LeetCode - Hard - 23. Merge k Sorted Lists

Topic

Linked List
Divide and Conquer
Heap

Description

https://leetcode.com/problems/merge-k-sorted-lists/

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won’t exceed 10^4.

Analysis

LeetCode 21. Merge Two Sorted Lists的延伸。

Submission

import com.lun.util.SinglyLinkedList.ListNode;
public class MergeKSortedLists { 
    public ListNode mergeKLists(ListNode[] lists) { 
        ListNode result = null;
        if (lists == null)
            return result;
        for (ListNode list : lists) { 
            result = mergeTwoList(result, list);
        }
        return result;
    }
    private ListNode mergeTwoList(ListNode l1, ListNode l2) { 
        if (l1 == null) { 
            return l2;
        } else if (l2 == null) { 
            return l1;
        } else if (l1.val < l2.val) { 
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        } else { 
            l2.next = mergeTwoList(l1, l2.next);
            return l2;
        }
    }
}

Test

import static org.junit.Assert.*;
import static com.lun.util.SinglyLinkedList.*;
import org.junit.Test;
import com.lun.util.SinglyLinkedList.ListNode;
public class MergeKSortedListsTest { 
    @Test
    public void test() { 
        MergeKSortedLists obj = new MergeKSortedLists();
        ListNode[] lists1 = { ints2List(1, 4, 5), ints2List(1, 3, 4), ints2List(2, 6)};
        ListNode expected1 = ints2List(1, 1, 2, 3, 4, 4, 5, 6);
        assertTrue(areTwoListEqual(obj.mergeKLists(lists1), expected1));
        ListNode[] list2 = null;
        assertNull(obj.mergeKLists(list2));
        ListNode[] list3 = { };
        assertNull(obj.mergeKLists(list3));
    }
}