Merge k Sorted Lists

1. Problem Description

Merge k sorted linked lists into one sorted linked list. Analyze and describe the complexity.

2. Approach

1. Approach 1
   • Brute force
   • Traverse all linked lists and store all values in an array
   • Sort the array and then create a new linked list
2. Approach 2
   • Merge sort
   • Split the list array in half recursively until only one linked list remains, which is naturally sorted
   • Then merge the linked lists

3. Implementation

3.1. Brute Force

// Time: O(NlogN)
// Space: O(N)
func mergeKLists(lists []*ListNode) *ListNode {
	data := make([]int, 0)
	for _, head := range lists {
		for head != nil {
			data = append(data, head.Val)
			head = head.Next
		}
	}

	sort.Ints(data)
	dummyHead := &ListNode{}
	current := dummyHead
	for _, datum := range data {
		current.Next = &ListNode{
			Val:  datum,
			Next: nil,
		}
		current = current.Next
	}

	return dummyHead.Next
}

3.2. Merge Sort

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 { return nil }
    if len(lists) == 1 { return lists[0]}

    left := mergeKLists(lists[:len(lists)/2])
    right := mergeKLists(lists[len(lists)/2:])
    return merge2Lists(left, right)
}

func merge2Lists(left, right *ListNode) *ListNode {
    dummyHead := &ListNode{}
    d := dummyHead
    for left != nil && right != nil {
        if left.Val < right.Val {
            d.Next = left
            d = d.Next
            left = left.Next
        }else {
            d.Next = right
            d = d.Next
            right = right.Next
        }
    }

    if left != nil {
        d.Next = left
    }
    if right != nil {
        d.Next = right
    }
    return dummyHead.Next
}

4. References

• Merge k Sorted Lists - NowCoder
• 23. Merge k Sorted Lists - LeetCode