台州网站建设优化,重庆城乡规划和建设局网站,外贸网站模板免费下载,浅谈电子商务网站建设与管理前言#xff1a; 大家好#xff0c;我是良辰丫#x1f680;#x1f680;#x1f680;#xff0c;今天与大家一起做两道牛客网的链表题#xff0c;好久写关于链表题的博客了#xff0c;这两道题可以帮大家巩固一下链表知识#xff0c;我把两道题的链接放到下面#xf… 前言 大家好我是良辰丫今天与大家一起做两道牛客网的链表题好久写关于链表题的博客了这两道题可以帮大家巩固一下链表知识我把两道题的链接放到下面大家可以去做一下。 题目链接 合并两个排序链表 合并K个排序链表 个人主页良辰针不戳 所属专栏EveryDay学java 励志语句生活也许会让我们遍体鳞伤但最终这些伤口会成为我们一辈子的财富。 期待大家三连关注点赞收藏。 作者能力有限也会出错希望大家可以指正。 愿与君为伴共探Java汪洋大海。 目录1、合并两个排序链表1.1 题目描述1.2 实例1.3 题目分析1.4 代码展示2、合并K个排序链表2.1 题目描述2.2 实例2.3 题目分析2.4 代码展示与分析1、合并两个排序链表
1.1 题目描述 输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。数据范围 0 \le n \le 10000≤n≤1000-1000 \le 节点值 \le 1000−1000≤节点值≤1000 要求空间复杂度 O(1)O(1)时间复杂度 O(n)O(n)如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示 1.2 实例 输入 {1,3,5},{2,4,6} 返回值 {1,2,3,4,5,6} 1.3 题目分析 做题不能着急一定先要读懂题。 这个题目的要求是合并两个有序链表而且合并后的链表也是有序的。 做题要学的是思想今天我们主要用到的是虚拟节点。 申请一个虚拟的头结点cur指向这个虚拟头结点while循环进行进行遍历只要其中一个链表为空结束循环循环里面进行判断list1和list2谁较小就与cur进行拼接结束循环后说明至少有一个链表为空因此cur拼接不为空的链表也可能两个都为空至少拼接一个因为链表要以null结束。 1.4 代码展示 下面是具体代码我也会稍微写一点注释帮助大家理解。 public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//申请虚拟节点ListNode newHead new ListNode(-1);//cur指向当前的虚拟节点ListNode cur newHead;//while循环,只要遍历完其中一个链表就结束循环while(list1 ! null list2 ! null){if (list1.val list2.val){//拼接cur.next list1;cur cur.next;list1 list1.next;} else {//拼接cur.next list2;cur cur.next;list2 list2.next; }}//拼接不为空的两个都遍历完的时候任意拼接一个if(list1 ! null){cur.next list1;}else{cur.next list2;}return newHead.next;}
}
2、合并K个排序链表 聪明的大家或许已经发现这道题是刚刚那道题的升级版牛客网标注着难题的标志其实也没那么难找到了规律掌握了思想做起来很容易。 2.1 题目描述 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。数据范围节点总数 0 \le n \le 50000≤n≤5000每个节点的val满足 |val| 1000∣val∣1000 要求时间复杂度 O(nlogn)O(nlogn) 2.2 实例 输入 [{1,2},{1,4,5},{6}] 返回值 {1,1,2,4,5,6} 2.3 题目分析 做题除了要看懂题还要注意思想不要忙于去做题。 先去分析想明白用什么方法去做。 首先大家肯定会想到粗鲁的办法从前往后依次遍历比较然后进行拼接这样不仅时间复杂度高而且比较麻烦搞的头晕目眩也不一定能得出正确的答案。那么我们需要想到另一种方法分治思想这种思想我们在快排和归并排序中见过既然接触过我们肯定有点基础我们来回忆一下所谓的分治思想。 分治就是分而治之可以这样理解解决一个大问题的时候首先把大问题化解成若干个小问题小问题与大问题的性质保持一致逐个解决完小问题然后合并最终就解决了所谓的大问题。 总结分治思想 大问题化解为若干个子问题。计算各个子问题。合并所有子问题的解。 看到这里大家应该对分治思想有了一定的认识那么接下来我们分析一下这道题。 大问题化解成小问题需要写一个小问题的递归方法因此我们构造了func(ArrayList lists,int left ,int right)方法。分治思想需要注意边界这里的左边界和右边界是以链表为单位的而不是节点。我们还需要一个合并两个有序链表的方法在上面那道题就是我们可以直接复制过来。 2.4 代码展示与分析 下面是合并k个有序链表的代码我会通过注释带大家简单分析一下。 public class Solution {public ListNode mergeKLists(ArrayListListNode lists) {//需要返回一个节点//传参func参数为集合lists左边界0和右边界lists.size()-1return func(lists,0,lists.size()-1);}//下面是一个递归方法//也就是大问题化解为小问题的过程private ListNode func(ArrayListListNode lists,int left ,int right){//左边界大于右边界的时候化解结束if(left right){return null;//左边界等于右边界的时候返回该节点//因为这里左右节点的下标相同//所以写lists.get(left)或者lists.get(right)都行} else if(left right){return lists.get(left);//left right的时候就要再次进行划分//因为咱们只有合并两个链表的方法} else{int mid (left right) / 2;return merge(func(lists,left,mid),func(lists,mid1,right));}}//下面的方法就是第一道题的答案就不做详细说明了private ListNode merge(ListNode list1,ListNode list2){ListNode newHead new ListNode(-1);ListNode cur newHead;while(list1 ! null list2 ! null){if(list1.val list2.val){cur.next list1;cur cur.next;list1 list1.next;} else {cur.next list2;cur cur.next;list2 list2.next;}}if(list1 null){cur.next list2;} else {cur.next list1;}return newHead.next;}
}后序 我相信大家通过这两道题学到了很多第一道题比较简单但大家不要眼高手低还是多加练习熟能生巧第二道题需要掌握分治思想可能大家一看到递归就会头疼代码不多但是却不容易理解这个东西需要多加练习琢磨画图需要自己不断去品味去感受不要畏惧做的多了你会感到所谓的递归其实没有那么难。哈哈今天的内容到这里也就结束了希望小小的我能够帮助到大家。
