LeetCode - Hard - 23. Merge k Sorted Lists

╰半橙微兮° 2023-01-06 05:41 119阅读 0赞

## Topic ##

*  Linked List
 *  Divide and Conquer
 *  Heap

## Description ##

[https://leetcode.com/problems/merge-k-sorted-lists/][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));
    	}
    }

[https_leetcode.com_problems_merge-k-sorted-lists]: https://leetcode.com/problems/merge-k-sorted-lists/
[LeetCode 21. Merge Two Sorted Lists]: https://leetcode.com/problems/merge-two-sorted-lists