# 23. Merge k Sorted Lists

## Description

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters `1` or `0`.

Example 1:

``````Input: a = "11", b = "1"
Output: "100"
``````

Example 2:

``````Input: a = "1010", b = "1011"
Output: "10101"
``````

Tags: Math, String

## 题解

### 思路1

• 1.遍历所有链表将值存到数组中
• 2.对数组进行排序
• 3.将排序好的数组转化为链表

• 时间复杂度
• 将链表转化为数组需要O(N)的时间
• 对数组排序需要O(N log N)的时间
• 将数组转化为链表需要O(N)的时间
• 空间复杂度
• 排序需要O(n)的空间
• 数组转化为链表需要O(N)的空间
``````func mergeKLists(lists []*ListNode) *ListNode {
nums := make([]int, 0, 10)

//    1.链表转化为数组
for _, v := range lists {
nums = append(nums, MarshalListNodeToSlice(v)...)
}
//    对数组排序
nums = QuickSort(nums)

//    将数组转化为链表
return MarshalSliceToListNode(nums)
}
//  其他详细代码在此目录的Solution.go文件内
``````

### 思路2

• 依次在没个链表中寻找最小的依次合并到一个链表作为结果
``````

``````

### 思路3

• 依次在没个链表中寻找最小的依次合并到一个链表作为结果,但是要用队列 ```go func mergeKLists3(lists []ListNode) ListNode { pq := make(ListNodeQueue, len(lists)) for i := range lists {
``````  pq[i] = lists[i]
``````
} heap.Init(&pq) if pq.Len() < 1 {
``````  return nil
``````
}
``````result := heap.Pop(&pq).(*ListNode)
if result == nil {
return result
}
if result.Next != nil {
heap.Push(&pq, result.Next)
}
tail := result
for pq.Len() > 0 {
tail.Next = heap.Pop(&pq).(*ListNode)
tail = tail.Next
if tail == nil {
break
}
if tail.Next != nil {
heap.Push(&pq, tail.Next)
}
}

return result
``````

}

``````
### 思路4
> 依次合并
- 依次在没个链表中寻找最小的依次合并到一个链表作为结果

```go
``````