023 合并K个排序链表

题目

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

示例:

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

实现

第一种:两两合并的方式

构造合并两个有序链表得到一个新的有序链表的方法:ListNode MergeTwoLists(ListNode l1, ListNode l2)。可以使用该方法合并前两个有序链表得到一个新的有序链表,之后把这个新链表与第三个有序链表合并,依次类推,最后得到合并K个有序列表的新列表。

  • 执行结果:通过
  • 执行用时:256 ms, 在所有 C# 提交中击败了 36.69% 的用户
  • 内存消耗:29.3 MB, 在所有 C# 提交中击败了 18.37% 的用户
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) 
    {
        ListNode pHead = new ListNode(int.MaxValue);
        ListNode temp = pHead;

        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
            {
                temp.next = l1;
                l1 = l1.next;
            }
            else
            {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }

        if (l1 != null)
            temp.next = l1;

        if (l2 != null)
            temp.next = l2;

        return pHead.next;
    }
    
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists.Length == 0)
            return null;

        ListNode result = lists[0];
        for (int i = 1; i < lists.Length; i++)
        {
            result = MergeTwoLists(result, lists[i]);
        }
        return result;
    }
}

第二种:选择值最小结点的方式

C# 语言

  • 执行结果:通过
  • 执行用时:776 ms, 在所有 C# 提交中击败了 7.10% 的用户
  • 内存消耗:29.2 MB, 在所有 C# 提交中击败了 22.45% 的用户
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public ListNode MergeKLists(ListNode[] lists) 
    {
        int len = lists.Length;
        if (len == 0)
            return null;

        ListNode pHead = new ListNode(-1);
        ListNode temp = pHead;
        while (true)
        {
            int min = int.MaxValue;
            int minIndex = -1;
            for (int i = 0; i < len; i++)
            {
                if (lists[i] != null)
                {
                    if (lists[i].val < min)
                    {
                        minIndex = i;
                        min = lists[i].val;
                    }
                }
            }
            if (minIndex == -1)
            {
                break;
            }
            temp.next = lists[minIndex];
            temp = temp.next;
            lists[minIndex] = lists[minIndex].next;
        }
        return pHead.next;        
    }
}

Python 语言

  • 执行结果:通过
  • 执行用时:7772 ms, 在所有 Python3 提交中击败了 5.02% 的用户
  • 内存消耗:16.5 MB, 在所有 Python3 提交中击败了 44.31% 的用户
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import sys
        count = len(lists)
        if count == 0:
            return None
        pHead = ListNode(-1)
        temp = pHead
        while True:
            minValue = sys.maxsize
            minIndex = -1
            for i in range(count):
                if lists[i] is not None:
                    if lists[i].val<minValue :
                        minIndex = i
                        minValue = lists[i].val
            if minIndex == -1:
                break
            temp.next = lists[minIndex]
            temp = temp.next
            lists[minIndex] = lists[minIndex].next
        return pHead.next
浙ICP备19012682号