#23 Merge k Sorted Lists——Top 100 Liked Questions

悠悠 2022-02-02 13:27 152阅读 0赞

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

**Example:**

Input:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6

> """
> 
> 第一次：两两合并
> 
> """ 
> 
>     # Definition for singly-linked list.
>     # class ListNode(object):
>     #     def __init__(self, x):
>     #         self.val = x
>     #         self.next = None
>     
>     class Solution(object):
>         
>         def mergeTwoList(self, l1, l2):
>             head = ListNode(0)
>             p = head
>             while l1 and l2:
>                 if l1.val <= l2.val:
>                     p.next = ListNode(l1.val)
>                     p = p.next
>                     l1 = l1.next
>                 else:
>                     p.next = ListNode(l2.val)
>                     p = p.next
>                     l2 = l2.next
>             if l1:
>                 p.next = l1
>             if l2:
>                 p.next = l2
>             return head.next
>         
>         def mergeKLists(self, lists):
>             """
>             :type lists: List[ListNode]
>             :rtype: ListNode
>             """
>             if lists == []:
>                 return None
>             L = len(lists)
>             res = lists[0]
>             for i in range(1, L):
>                 res = self.mergeTwoList(res, lists[i])
>             return res
> 
> """
> 
> Time Limit Exceeded
> 
> """

> """
> 
> 第二次：辅助列表sortHeadList，里边保存以每个node作为head的链表，以分理出每个node，然后对数组进行排序，
> 
> 对排序后的数组再进行处理
> 
> """ 
> 
>     # Definition for singly-linked list.
>     # class ListNode(object):
>     #     def __init__(self, x):
>     #         self.val = x
>     #         self.next = None
>     
>     class Solution(object):
>         
>         def mergeKLists(self, lists):
>             """
>             :type lists: List[ListNode]
>             :rtype: ListNode
>             """
>             if lists == []:
>                 return None
>             if len(lists) == 1:
>                 return lists[0]
>             sortHeadList = []
>             for head in lists:
>                 p = head
>                 while p:
>                     print('ok')
>                     sortHeadList.append(p)
>                     p = p.next
>             
>             sortHeadList = sorted(sortHeadList, key = lambda x: x.val)
>             if len(sortHeadList) == 0: 
>                 return None
>             res = sortHeadList[0]
>             pp = res
>             for i in range(1, len(sortHeadList)):
>                 pp.next = sortHeadList[i]
>                 pp = pp.next
>             return res
> 
> """
> 
> Runtime: 92 ms, faster than 67.58% of Python online submissions for Merge k Sorted Lists.
> 
> Memory Usage: 17.5 MB, less than 35.49% of Python online submissions for Merge k Sorted Lists.
> 
> """

递归的学习要提上日程了！