本文主要是介绍23.合并K个升序链表-----力扣,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目:
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
题目链接
二、示例:
输入: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示例 2:
输入:lists = [] 输出:[]示例 3:
输入:lists = [[]] 输出:[]
三、分析:
(1)什么是链表:
链表是一种常见的数据结构,它由一系列节点组成,这些节点通过指针连接。每个节点包含两部分:数据和指向下一个节点的指针(next)。链表的特点是它的元素在内存中不必连续存储,每个节点可以存储任意类型的数据,并且节点可以动态地添加和删除。
优点:
链表的优点是插入和删除操作的时间复杂度为O(1),而数组的插入和删除操作的时间复杂度为O(n),其中n为元素个数。
缺点:
链表的缺点是访问某个位置的元素需要遍历整个链表,时间复杂度为O(n),而数组的访问操作的时间复杂度为O(1)。
用途:
链表常用于需要频繁进行插入和删除操作的场景,例如实现队列、栈等数据结构,或者用于解决某些特定的问题。
由题可知,题目提供了一个链表数组,且它们都已经做了升序排列处理。让我们将它们合并在同一个升序链表中,并返回。由上面的题目和示例可知,只要我们将链表数组中的每个数组中的数据合并在一起、升序,就能得到正确答案。事实上,是这样吗?
(2)请看下面代码:
class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length == 0) return null; //如果链表数组为空,返回ListNode ls=new ListNode(); //创建对象,用于获取数组中的对象ListNode ks=new ListNode(); //创建对象,用于存储结果List<Integer>p=new ArrayList<>(); //创建一个list集合,用于存储中途的各个数组元素int len=lists.length; //获取链表数组长度,用于循环for(int i=0;i<len;i++){ls=lists[i];while(ls!=null){p.add(ls.val); //添加元素ls=ls.next; //下一个对象}}if(p.isEmpty()) return null; //如果集合为空,说明数组里没有对象Collections.sort(p); //排序for(int i=p.size()-1;i>=0;i--){if(i==p.size()-1){ //插入最后一个元素,ks=new ListNode(p.get(i)); //不再需要next}else {ks=new ListNode(p.get(i),ks); //插入其它元素}}return ks; //返回结果}
}
(3)运行结果如图:
由上图结果可知,上述的解题思路是可以被采纳的。当然,除了用java语言来解决这道题外,还可以用c++来解决这道题。
四、其它解题方法:
(1)如图是一个链表节点:
由上面对链表的介绍得知,链表每个节点包含两部分:数据和指向下一个节点的指针(next)。
(一)、数据部分就是用来存储数据的,支持任意类型的数据;
(二)、next指针部分用来指向下一个节点的,节点与节点之间的连接枢纽。
(2)分析:
由上面我们已经对链表有了一定的了解。我们首先需要对题目提供的链表数组中的每个数据进行排序,在排序结束后,此时创建一个链表——用于存储结果。在进行将数据插入链表操作的时候,需要将已经插入的数据从原集合中删除,同时替换数据。因为用的是set有序集合来对数据进行排序(升序),每次取其头部数据(最小值)插入。最后,调整链表,同时插入已经替换的数据到链表中。
(3)请看下面代码:
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {typedef pair<int,int>pir; //pair用于可以插入重复数据set<pir>s; //set用于排序for(int i=0;i<lists.size();i++){if(lists[i]==NULL)continue; //判空s.insert(pir(lists[i]->val,i)); //将链表中的值插入set中,i为第几个链表的序号}ListNode new_head,*p=&new_head,*q; //有头链表new_head.next=nullptr; //初始化头节点next指针while(s.size()){//集合元素不为空pir a=*s.begin(); //每一次取出头部数据s.erase(s.begin());//并且删除q=lists[a.second]; //表示第a.second个链表中的第一个节点(先取)lists[a.second]=lists[a.second]->next;//后将其替换p->next=q; //将q节点连接到p节点后面q->next=nullptr; //初始化q的next指针p=q; //p指向结果的最后一位,用于下次插入的节点将能够连接到q的next指针if(lists[a.second]){ //将第a.second个链表中的第一个节点插入,s.insert(pir(lists[a.second]->val,a.second)); //这个节点是已经替换掉的,不是原节点}}return new_head.next; //返回头节点}
};
(四)运行结果如图:
文章到此结束!
这篇关于23.合并K个升序链表-----力扣的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!