LeetCode题目之腾讯精选练习（50题）：合并K个排序链表

青旅半醒 2024-04-17 23:01 69阅读 0赞

# 题目 #

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

**示例**:

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

## 实现代码 ##

public ListNode MergeKLists(ListNode[] lists)
    {
        
        var listHead = new ListNode(0);
        ListNode curr = listHead;
        int min, temp, minList = 0;
        while (lists.Any(i => i != null))
        {
        
            min = int.MaxValue;
            for (int i = 0; i < lists.Length; i++)
            {
        
                if (lists[i] == null)
                    continue;
                temp = lists[i].val;
                if (temp < min)
                {
        
                    min = temp;
                    minList = i;
                }
            }
            curr.next = new ListNode(min);
            lists[minList] = lists[minList].next;
            curr = curr.next;
        }
        return listHead.next;
    }

## 执行结果 ##

**执行结果**：通过  
**执行用时** : 796 ms, 在所有 C\# 提交中击败了17.14%的用户  
**内存消耗** : 27.6 MB, 在所有 C\# 提交中击败了8.51%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

开始对合并两个有序链表进行了改进，变成了合并k个有序链表，结果虽然通过，但是效率不是很高。之后看解答了解到了分治法，直接对之前的函数调用，进行两两合并，效率更加高。

## 改进的方法 ##

**分治法**：

public ListNode MergeKLists(ListNode[] lists)
    {
        
        int len = lists.Length;
        int interval = 1;
        while (interval < len)
        {
        
            for (int i = 0; i < len - interval; i += interval * 2)
            {
        
                lists[i] = MergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        if (len > 0)
            return lists[0];
        else
            return null;
    }
    public ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        
        var listHead = new ListNode(0);
        ListNode curr = listHead;
        int x, y;
        while (l1 != null || l2 != null)
        {
        
            x = (l1 != null) ? l1.val : int.MaxValue;
            y = (l2 != null) ? l2.val : int.MaxValue;
            if (x < y)
            {
        
                curr.next = new ListNode(x);
                if (l1 != null) l1 = l1.next;
            }
            else
            {
        
                curr.next = new ListNode(y);
                if (l2 != null) l2 = l2.next;
            }
            curr = curr.next;
        }
        return listHead.next;
    }

## 执行结果 ##

![在这里插入图片描述][20190902175704669.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c7ef9360422a454c883bfb54c90219e7.png
[20190902175704669.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/92c81c48d6d34185a3f135db6f8d8343.png