Leetcode题库——23.合并k个排序链表

@author: ZZQ

@software: PyCharm

@file: mergeKLists.py

@time: 2018/10/12 19:55

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

示例：

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

思路：两两合并再合并，判断奇偶，每次用一个新的数组来存放当前经过合并后的新的链表首节点，时间复杂度：O(nlogn)

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def mergeTwoLists(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

        """

        if l1 is None and l2 is None:

            return None

        if l1 is None:

            return l2

        if l2 is None:

            return l1

        l3 = ListNode(0)

        head = l3

        while l1 is not None and l2 is not None:

            if l1.val > l2.val:

                l3.next = l2

                l2 = l2.next

            else:

                l3.next = l1

                l1 = l1.next

            l3 = l3.next

        if l1 is not None and l2 is None:

            l3.next = l1

        if l1 is None and l2 is not None:

            l3.next = l2

        return head.next

    def mergeKLists(self, lists):

        """

        :type lists: List[ListNode]

        :rtype: ListNode

        """

        if len(lists) == 0:

            return None

        cur_list = lists

        while len(cur_list) > 1:

            cur_temp_list = []

            if len(cur_list) % 2:

                for i in range((len(cur_list) - 1) / 2):

                    cur_temp_list.append(self.mergeTwoLists(cur_list[i * 2], cur_list[i * 2 + 1]))

                cur_temp_list.append(cur_list[len(cur_list)-1])

            else:

                for i in range(len(cur_list) / 2):

                    cur_temp_list.append(self.mergeTwoLists(cur_list[i * 2], cur_list[i * 2 + 1]))

            cur_list = cur_temp_list

        return cur_list[0]

巴特西

Leetcode题库——23.合并k个排序链表

最新文章

热门文章