23 合并k个升序列表

本文主要是介绍23 合并k个升序列表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

题目链接：
https://leetcode-cn.com/problems/merge-k-sorted-lists/

解法：两两合并
思路：这道题的基础是合并两个升序链表，只要会合并两个升序链表，合并 k 个也差不多。
声明一个头结点，然后对链表数组进行遍历，把每次合并结果的头结点，跟下一个链表进行合并，最后得到合并k个链接的结果

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0 ; i < lists.length; i++) {
            ans = mergetTwoLists(ans, lists[i]);
        }
        return ans;
    }

    private ListNode mergetTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        ListNode aPtr = a;
        ListNode bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        // 把剩余的节点拼在后面
        tail.next = aPtr != null ? aPtr : bPtr;
        return dummyHead.next;
    }
}

提交通过了，但是击败率有点低啊，用Go语言试试

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeKLists(lists []*ListNode) *ListNode {
	var ans *ListNode
	for i := 0; i < len(lists); i++ {
		ans = mergeTwoLists(ans , lists[i]);

	}
	return ans
}

func mergeTwoLists(a *ListNode, b *ListNode ) *ListNode {
	// go语言没有三目表达式
	if a == nil || b == nil {
		if  a != nil {
			return  a
		} else {
			return b
		}
	}
	dummyHead := &ListNode{
		Val:  0,
		Next: nil,
	}
	var tail = dummyHead
	var aPtr = a
	var bPtr = b
	
	// go语言没有while循环
	for {
		if aPtr == nil || bPtr == nil  {
			break
		}

		if aPtr.Val  < bPtr.Val {
			tail.Next = aPtr
			aPtr = aPtr.Next
		} else {
			tail.Next = bPtr
			bPtr = bPtr.Next
		}
		tail = tail.Next
	}
    
	if aPtr != nil {
		tail.Next = aPtr
	} else {
		tail.Next = bPtr
	}

	return dummyHead.Next;

}

我使用了 go 语言，但是比不上别人go语言的结果，为什么呢？因为时间复杂度不是最优的，上面解法的复杂度如下：
时间复杂度：O(k^2 * n)
空间复杂度：O(1)

采用分治法或者优先队列可以把 k^2 优化为 k*logk，别人应该是采用了更优的解法

看官方题解就能解了：
https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/

日期：2021-12-04

这篇关于23 合并k个升序列表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！