网站加急备案,青岛在线制作网站,精通网站建设需要学什么,店铺设计素材前提知识#xff1a;1.画图#xff0c;数据结构相关的题#xff0c;画图必不可少#xff0c;只要能画出来#xff0c;那么后面的代码就很容易能写出来#xff0c;因为将抽象的数据结构转换为直观的图画2.引入虚拟头结点#xff0c;也叫哨兵位#xff0c;能够避免考虑很…前提知识1.画图数据结构相关的题画图必不可少只要能画出来那么后面的代码就很容易能写出来因为将抽象的数据结构转换为直观的图画2.引入虚拟头结点也叫哨兵位能够避免考虑很多边界情况3.不要吝啬空间如果你看到第二点的时候如果反应是有些题也可以不用虚拟节点就能解决时其实这就已经是有点吝啬空间的思想了一个虚拟头结点才几个字节根本不需要考虑大胆创建就行了4.快慢双指针链表中经常且好用的方法5.链表常用存在创建节点头插尾插其中头插是比较重要的因为通过头插可以直接完成逆序链表的操作而很多题目中都需要逆序链表所以头插的操作要掌握同时又结合虚拟头结点那么头插起来会非常方便题目一算法原理题意很简单就是模拟加法的操作只不过链表是逆序的但是不要看是逆序的就觉得有难度如果是正序的反而要更难一点因为加法是从低位开始计算的而逆序链表刚好就把低位放在了头结点反而更好操作而正序链表如果要进行加法反而要先逆序再操作思路就是用两个指针指向两个链表的头结点然后开始往后遍历将两数的和相加并记录在一个变量t里面最后该位只取t的个位然后/10即可而循环遍历结束条件是两个指针都为空时且t也为0才结束其中为什么t也要为0是解决下面这种情况 即虽然两个指针为空但还有一个进位没有进也是可以用虚拟头结点直接进行加法操作后接在虚拟头结点之后就行代码
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//虚拟头结点ListNode newHeadnew ListNode(0);//双指针ListNode cur1l1,cur2l2,curnewHead;//记录进位int t0;//循环遍历while(cur1!null||cur2!null||t!0){//如果链表1还有值if(cur1!null){tcur1.val;cur1cur1.next;}//如果链表2还有值if(cur2!null){tcur2.val;cur2cur2.next;}//进位操作cur.nextnew ListNode(t%10);curcur.next;t/10;}//返回真正的头结点return newHead.next;}
}题目二算法原理题意很简单注意不能修改原结点的值只能通过移动结点进行修改如果还是用之前刚学链表时的思想那就是不创建虚拟结点同时也吝啬空间不定义变量还不画图的话那就脑袋里面慢慢绕了一不小心就绕混了因为如果不创建虚拟结点的话12这两个结点的操作和34之间的操作是不一样的34这里需要1这个结点指向4而12这里没有前面的结点因此需要自己找头结点导致12的时候要特殊处理不能进入循环而创建虚拟头结点就可以让12操作和后面一样如果创建虚拟结点后并画图但吝啬空间的话那么结点交换和修改就得考虑顺序且非常乱
class Solution {public ListNode swapPairs(ListNode head) {if(headnull){return head;}ListNode newHeadnew ListNode(0,head);ListNode prevnewHead,curhead;while(cur!nullcur.next!null){prev.nextcur.next;prevcur;ListNode tmpcur.next.next;cur.next.nextcur;cur.nexttmp;curtmp;}return newHead.next;}
} 这循环里面的代码顺序不能乱调且一眼看过去也很乱而直接定义变量的话就会这样那么逻辑就直接是prev指向nextnext指向curcur指向nnext且先后顺序随便根本不影响然后再修改变量这里需要注意顺序不然会出现覆盖非常清晰然后讨论循环终止条件偶数结点情况下可以发现如果curnull就终止奇数结点情况下 可以发现如果nextnull就终止代码
class Solution {public ListNode swapPairs(ListNode head) {//特殊处理空结点和单结点if(headnull||head.nextnull){return head;}ListNode newHeadnew ListNode(0,head);ListNode prevnewHead,curhead,nextcur.next,nnextnext.next;while(cur!nullnext!null){//修改结点指向prev.nextnext;next.nextcur;cur.nextnnext;//修改变量(注意顺序)prevcur;curnnext;if(cur!null){nextcur.next;}if(next!null){nnextnext.next;}}return newHead.next;}
}题目三算法原理这道题比较综合通过模拟可以发现无非是将前一半链表和后一半经过逆序的链表进行合并即可因此就涉及到三个知识点找链表中间结点逆序操作合并链表找链表中间结点采用快慢双指针来解决逆序链表采用头插来解决合并链表模拟操作即可需要注意的是找到中间结点后要将前后两个链表之间进行切断实现两个独立的链表才好方便进行后面的操作代码
class Solution {public void reorderList(ListNode head) {if(head.nextnull){return;}//找到中间结点ListNode slowhead;ListNode fasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}//拆开链表ListNode curhead;while(cur.next!slow){curcur.next;}cur.nextnull;curhead;//逆序链表ListNode newHeadnew ListNode();while(slow!null){ListNode slowNextslow.next;slow.nextnewHead.next;newHead.nextslow;slowslowNext;}//合并链表newHeadnewHead.next;while(cur!nullnewHead!null){ListNode curNextcur.next;ListNode newHeadNextnewHead.next;cur.nextnewHead;if(curNext!null){newHead.nextcurNext; } curcurNext;newHeadnewHeadNext;}}
}题目四 算法原理题意很简单就是按照升序合并k个链表而且还比较好心的帮我们把k个链表进行了升序操作我们之前学过合并2个链表所以最容易想到的就是暴力解法即遍历数组第1个链表和第2个链表合并之后再和第3个链表合并……时间复杂度上假设有k个链表每个链表长度为n合并的时间复杂度是n(k-1)n(k-2)……nO(nk^2)ON^3效率非常低所以要换一个方法方法一既然是比较大小进行排序那么就可以借助优先级队列来实现将每个链表的头结点都扔进去取出堆顶元素就是所有头结点中最小的然后对应的那个链表就扔下一个结点进去然后再取堆顶元素循环往复直到对应链表为空则停止添加最后当堆为空时则合并完成时间复杂度上堆的操作为log级别有k个链表所以要比较k次又总共有n个节点所以时间复杂度为On k logk代码一优先级队列
class Solution {public ListNode mergeKLists(ListNode[] lists) {//如果数组为空或者数组中的链表为空if(listsnull||lists.length0){return null;}//创建一个小根堆PriorityQueueListNode priorityQueuenew PriorityQueue((o1,o2)-o1.val-o2.val);//取出所有的头结点放进去for(ListNode node:lists){if(node!null){priorityQueue.offer(node);}}//创建一个虚拟节点ListNode newHeadnew ListNode();ListNode prevnewHead;//合并链表while(!priorityQueue.isEmpty()){ListNode curpriorityQueue.poll();prev.nextcur;prevcur;//如果该链表为空则不添加if(cur.next!null){priorityQueue.offer(cur.next);}}//返回头结点return newHead.next;}
}方法二既然合并k个链表可以拆分为n次合并2个链表那么子问题是一样的就可以采用分治递归的思想以归并排序来解决套模板即可代码二分治递归
class Solution {public ListNode mergeKLists(ListNode[] lists) {//要求对lists数组从下标0开始到lists.length-1之间的链表进行合并并返回头结点return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists,int left,int right){//如果为空区间if(leftright){return null;}//如果只有一个链表不用合并if(leftright){return lists[left];}//找到中间值分为[left,mid],[mid1,right]两个区间int mid(leftright)/2;//递归处理左右两部分ListNode l1merge(lists,left,mid);ListNode l2merge(lists,mid1,right);//合并两个链表ListNode newHeadnew ListNode();ListNode prevnewHead;while(l1!nulll2!null){if(l1.vall2.val){prev.nextl2;prevl2;l2l2.next;}else{prev.nextl1;prevl1;l1l1.next;}}if(l1!null){prev.nextl1;}if(l2!null){prev.nextl2;}//返回头结点return newHead.next;}
}题目五算法原理题意很简单就是不停翻转长度为k的链表直到全部翻转完或者剩余长度不够k则停止虽然是困难题但是模拟的操作并不难首先我们先遍历一遍链表统计出链表的长度然后再除k看看有多少组需要被翻转假设为n组然后循环n次每次循环代表每一组循环里面再嵌套循环k次表示将k个结点进行翻转最后拼接上后面未被翻转的结点翻转也就是逆序所以我们采用之前用的头插法其中需要注意的是每次头插翻转完一组后后面结点跟的是第一次头插的结点后面代码
class Solution {public ListNode reverseKGroup(ListNode head, int k) {//如果翻转长度为1则不用翻转if(k1){return head;}//遍历链表统计长度ListNode curhead;int len0;while(cur!null){curcur.next;len;}//如果长度不够k直接返回if(lenk){return head;}int nlen/k;//头插翻转curhead;ListNode newHeadnew ListNode(0);ListNode prevnewHead;ListNode tmpnull;//翻转n组for(int i0;in;i){//记录下一组的前驱结点tmpcur; for(int j0;jk;j){ ListNode nextcur.next; cur.nextprev.next;prev.nextcur;curnext;}//更新前驱节点prevtmp;}//拼接剩余节点prev.nextcur;//返回头结点return newHead.next;}
}
