1.1. 题目
1.1.1. 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
1.1.2. 题解:
- 合并两个有序链表的升级版
- 原链表都是有序的
1.1.3. 思路:
- 作弊法: 遍历所有的数据,放入到数组里,然后进行排序,然后再填充到链表里...
- 正常思路: 先去做一下 合并两个有序链表
- 依次遍历数组
- 可以每两个进行合并,得到新的数组链表,再继续合并到最后一个链表为止
- 也可以第一个和第二个合并,得新链表,然后新链表和第三个合并,一直合并到最后一个!
- 我用后面这个方法解的,因为我刚刚做完合并两个有序链表,可以拿来直接用
1.1.4. 代码:
点击显示
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 1 {
return lists[0]
}
var list *ListNode
for i:=0;i<len(lists);i++ {
if i == 0 {
list = mergeTwoLists(lists[0],lists[1])
i++
continue
}
list = mergeTwoLists(list,lists[i])
}
return list
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
newNode := &ListNode{Val:0}
head := newNode
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
newNode.Next = l2
l2 = l2.Next
} else {
newNode.Next = l1
l1 = l1.Next
}
newNode = newNode.Next
}
if l1 != nil {
newNode.Next = l1
}
if l2 != nil {
newNode.Next = l2
}
return head.Next
}
// 作弊法
func mergeKLists2(lists []*ListNode) *ListNode {
var values []int
listLen := len(lists)
if listLen == 0 {
return nil
}
for i:=0;i<listLen;i++ {
ls := lists[i]
for ls != nil {
values = append(values,ls.Val)
ls = ls.Next
}
}
sort.Sort(sort.IntSlice(values))
newList := &ListNode{
}
head := newList
for k,v := range values {
head.Next = &ListNode{
Val:v,
}
if k == len(values) {
head.Next = nil
}
head = head.Next
}
return newList.Next
}