# LeetCode: 23. Merge k Sorted Lists

## 题目¶

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

Example 2:

```Input: lists = []
Output: []
```

Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

## 解法¶

### 从头到尾挨个合并数组内的链表¶

1. 取第一个链表作为新的链表
2. 然后遍历数组，将数组元素跟新链表合并得到合并后的新链表（合并两个链表的详细说明详见前面的 LeetCode: 21. Merge Two Sorted Lists
3. 然后再用合并后的新链表跟下一个链表合并
4. 数组遍历完成后就得到了一个合并了所有链表的新链表

```# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
def mergeKLists(self, lists):
if not lists:
return None

new_list = None
for list in lists:
new_list = self.mergeTwoLists(new_list, list)

return new_list

def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1

dummy = ListNode()
tail = dummy

while l1 is not None and l2 is not None:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next

tail = tail.next

if l1 is None:
tail.next = l2
if l2 is None:
tail.next = l1

return dummy.next
```

### 使用首尾合并的方法加速合并¶

1. 两个指针，i 指向数组第一个元素，j 指向数组最后一个元素
2. 合并两个指针对应的链表，将合并后的结果保存到左边指针的数组索引位置
3. 相向移动两个指针，每移动一步就按上面的方法合并链表并保存结果
4. 当两个指针相遇时(i >= j 时, 数组元素个数为奇数是 i == j, 数组元素个数为偶数是 i - 1 == j)，将 i 移到数组第一个元素，继续按上面的方法首尾合并 i、j 处的链表
5. 当 i == j == 0 时，合并结束，此时数组的第一个元素的值即为完成合并后的新链表

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeKLists(self, lists):
if not lists:
return None

i = 0
j = len(lists) - 1
while i < j:
new_list = self.mergeTwoLists(lists[i], lists[j])
lists[i] = new_list
i += 1
j -= 1
if i >= j:
i = 0

return lists[0]

def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1

dummy = ListNode()
tail = dummy

while l1 is not None and l2 is not None:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next

tail = tail.next

if l1 is None:
tail.next = l2
if l2 is None:
tail.next = l1

return dummy.next
```