合并k个已排序的链表

1. 题目描述

k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。

2. 思路

1. 思路一
   • 暴力法
   • 遍历所有链表存储在数组里
   • 对数组排序之后创建一个新的链表
2. 思路二
   • 归并排序
   • 将链表数组对半分直至只有一个链表，自然有序
   • 接着对链表合并

3. 实现

3.1. 暴力法

//时间：O(NlogN)
//空间：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. 归并排序

/**
 * 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. 参考

• 合并k个已排序的链表_牛客题霸_牛客网
• 23. 合并K个升序链表 - 力扣（LeetCode）