23.H 合并 K 个升序链表

Problem: 23. 合并 K 个升序链表

思路

合并两个有序链表是很简单的，因此考虑分治法。先把K个链表分为两个部分，分别进行排序，最后再合并两个链表。

Code

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

	mid := len(lists) / 2
	part1 := mergeKLists(lists[0:mid])
	part2 := mergeKLists(lists[mid:])
	return mergeTwoLists(part1, part2)
}

func mergeTwoLists(head1 *ListNode, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{Val: -1}
	pre := dummyHead
	for head1 != nil && head2 != nil {
		if head1.Val < head2.Val {
			pre.Next = head1
			head1 = head1.Next
		} else {
			pre.Next = head2
			head2 = head2.Next
		}

		pre = pre.Next
	}

	if head1 != nil {
		pre.Next = head1
	} else {
		pre.Next = head2
	}

	return dummyHead.Next
}