## LinkedList - 23. Merge k Sorted Lists

Updated on with 0 views and 0 comments
1. 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

golang:

``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}

return merge(lists, 0, len(lists) - 1)
}

func merge(lists []*ListNode, left, right int) *ListNode {
if left == right {
return lists[left]
}

// 二分
mid := (right - left ) / 2 + left
l := merge(lists, left, mid)
r := merge(lists, mid+1, right)

var dummy = &ListNode{}
var cur = dummy

for l != nil && r != nil {
if l.Val < r.Val {
cur.Next = l
l = l.Next
} else {
cur.Next = r
r = r.Next
}
cur = cur.Next
}

if l != nil {
cur.Next = l
}
if r != nil {
cur.Next = r
}

return dummy.Next
}
``````
``````/**

* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
return helper(lists, 0, lists.length - 1);
}

private ListNode helper(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];

int mid = (end - start) / 2 + start;
ListNode first = helper(lists, start, mid);
ListNode second = helper(lists, mid + 1, end);

while (first != null && second != null) {
if (first.val < second.val) {
cur.next = first;
first = first.next;
} else {
cur.next = second;
second = second.next;
}
cur = cur.next;
}
if (first == null)
cur.next = second;
if (second == null)
cur.next = first;