LeetCode23合并K个排序链表

发表于 | 更新于 | 分类于 |
合并K个排序链表

题目描述：

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路：

  1. 如果将链表的排序转为数组的排序，那就很简单了。将所有链表中的数据值导入到List中，对list进行排序，最后再生成新的链表即可
  2. 使用一个数据记录着K个链表的头，每次取头部最小的，加入到我们新建的链表中。取出一个头之后，指针后移，删除当前头，直到比较完所有的头，得到新的链表即可。

这题在网站上没法调试。我使用第一个方法写的code一直会被这样的测试用例卡住：

...]```。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

我的代码是能处理正常情况的，这样的我就不处理了。这个输入与题目描述的根本不准确



### 我的解答：

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        first = ListNode(0)
        
        if len(lists) == 1:
            return lists[0]
        
        arr = []
        for item in lists:
            first = item
            arr.append(first.val)
            while first.next is not None:
                first = first.next
                arr.append(first.val)
            
        arr.sort()
        
        head = ListNode(0)
        pointer = ListNode(0)
        pointer = head
        
        for item in arr:
            pointer.next = ListNode(item)
            pointer = pointer.next
        
        return head.next