【LeetCode】23. Merge k Sorted Lists 基于Java的解法

「爱情、让人受尽委屈。」 2022-08-23 00:51 115阅读 0赞

23. Merge k Sorted Lists

Total Accepted: 88102 Total Submissions: 372066 Difficulty: Hard

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

# **【题意】** #

将K个已经排序的链表合并成一个排序的链表，分析并描述所用算法的复杂度。

# **【分析】** #

## 解法一：基于“二分”思想的归并排序 ##

初见之下，最容易想到的方法是“归并排序”（Merging Sort）：将两个或两个以上的有序表组合成一个新的有序表，无论是顺序存储结构还是链式存储结构，对于任何两个长度分别为m和n的有序表，其组合都可在O(m+n)的时间复杂度量级上完成。对于K个有序表，假设共有N个元素，且这些有序表初始状态都不为空，每个有序表平均拥有N/K个元素。最常用的方法是采用“二分”的思想进行两两合并：第一轮循环，有序表lists\[0\]与lists\[(K+1)/2\]，lists\[1\]与lists\[(K+1)/2+1\]，lists\[2\]与lists\[(K+1)/2+2\]....，lists\[K/2-1\]与lists\[K-1\]。这样K个有序表就被组合成了K/2个有序表；第二轮循环后将减少为K/4个有序表；直到组合成一个具有N个元素的有序表。总的时间复杂度：O(NKlogK)。

## **解法二：基于优先级队列的“堆排序”** ##

堆(Heap)的定义如下：n个元素的序列\{k1,k2,k3,...,kn\}当且仅当满足下列关系时，称为堆，

![Center][]

其中前者称为最小堆，后者称为最大堆。在Java中，堆是一种可以自我调整的二叉树，对于最小堆来说，对树执行删除和添加操作，可以让最小元素移动到根节点。在Java中，优先级队列（Priority Queue）便采用了“堆”这种数据结构，PriorityQueue是一个泛型类，它可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供比较器的对象（优先级队列实现排序中也需要比较）。

基于优先级队列，我们可以将K个链表的头结点全部添加到队列，由于优先级队列采用了最小堆数据结构，堆顶为队列的最小元素，我们将其取出添加到结果链表中，取出元素对应的链表下移一个节点，并将这个节点添加到优先级队列中；然后我们继续取出堆顶元素，...，直到优先级队列为空，那么其中所有元素取尽，K个链表的元素已经全部排序到结果链表。

# **【程序】** #

##  一、基于“二分”思想的归并排序（Java实现） ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution
    {
    public ListNode mergeKLists(ListNode[] lists)
    	{
    		int len=lists.length;
    		
    		if(lists==null||len==0)
    			return null;
    		if(len==1)
    			return lists[0];
    		
    		while(len>1)//基于“二分”思想进行链表的两两组合
    		{
    			int mid=(len+1)/2;//二分
    		    for(int i=0;i<len/2;i++)
    		    {
    		    	lists[i]=mergeTwoLists(lists[i],lists[i+mid]);
    		    }
    		    len=mid;
    		}
    		return lists[0];
    	}
    	//有序链表的组合，L1和L2为头结点，归并排序的核心思想
    	public ListNode mergeTwoLists(ListNode L1,ListNode L2)
    	{
    		if(L1==null)return L2;
    		if(L2==null)return L1;
    		
    		ListNode head=new ListNode(0);//保存结果的链表，头结点初始化
    		ListNode phead=head;
    		
    		while(L1!=null&&L2!=null)//两个链表归并排序
    		{
    			if(L1.val <=L2.val)
    			{
    				phead.next=L1;//接入结果链表
    				phead=phead.next;//移动指针
    				L1=L1.next;
    			}
    			else
    			{
    				phead.next=L2;
    				phead=phead.next;
    				L2=L2.next;
    			}
    		}
    		if(L1!=null)
    			phead.next=L1;
    		else
    			phead.next=L2;
    		
    		return head.next;//初始化的第一个节点不属于结果
    	}
    }

运行结果：

![Center 1][]

##  二、基于优先级队列的“堆排序”（Java实现） ##

class ListNode implements Comparable<ListNode>
    {
    	int value;
    	ListNode next;
    	ListNode(int val)
    	{
    		value=val;
    	}
    	
    	public int compareTo(ListNode other)
    	{
    		return value-other.value;
    	}
    }

//用优先级队列实现组合排序，其中优先级队列采用的数据结构为“最小堆”
    class Solution
    {
    	public ListNode mergeKLists(ListNode[] lists)
    	{
    		if(lists==null||lists.length==0)
    			return null;
    		if(lists.length==1)
    			return lists[0];
    		
    		 
    		PriorityQueue<ListNode> PQ=new PriorityQueue<ListNode>();
    		
    		ListNode head=new ListNode(0);
    		ListNode phead=head;
    		
    		for(ListNode list:lists)
    		{
    			if(list!=null)
    				PQ.offer(list);
    		}
    		while(!PQ.isEmpty())
    		{
    			ListNode temp=PQ.poll();
    			phead.next=temp;
    			phead=phead.next;
    			
    			if(temp.next!=null)
    				PQ.offer(temp.next);
    		}
    		return head.next;
    	}
    }

运行结果：

![Center 2][]

[Center]: /images/20220722/b948508224854981bd393c2331e6dddc.png
[Center 1]: /images/20220722/033376f5a6fb4494aef4b5b7471d6d98.png
[Center 2]: /images/20220722/5d55fed1d7f44721bd599c87f65e7700.png