题目
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
题目大意
合并 K 个有序链表
解题思路
借助分治的思想,把 K 个有序链表两两合并即可。相当于是第 21 题的加强版。
参考代码
package leetcode
// ListNode define
type ListNode = structures.ListNode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
length := len(lists)
if length < 1 {
return nil
}
if length == 1 {
return lists[0]
}
num := length / 2
left := mergeKLists(lists[:num])
right := mergeKLists(lists[num:])
return mergeTwoLists1(left, right)
}
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists1(l1.Next, l2)
return l1
}
l2.Next = mergeTwoLists1(l1, l2.Next)
return l2
}
标签:return,23,Lists,Next,Merge,l2,lists,l1,ListNode
From: https://blog.51cto.com/u_16110811/7106780