如何在网上注册公司网站,成立新公司取什么名字好呢,移动端设计规范,圣诞节网站模板文章目录一、链表题目的常用解题技巧总结二、两数相加解题思路代码实现及解析总结三、两两交换链表中的节点总结四、重排链表解题思路代码实现及解析总结五、合并 K 个升序链表解题思路代码实现及解析总结六、K 个一组翻转链表解题思路代码实现及解析总结一、链表题目的常用解题…文章目录一、链表题目的常用解题技巧总结二、两数相加解题思路代码实现及解析总结三、两两交换链表中的节点总结四、重排链表解题思路代码实现及解析总结五、合并 K 个升序链表解题思路代码实现及解析总结六、K 个一组翻转链表解题思路代码实现及解析总结一、链表题目的常用解题技巧总结画图—更加直观、清晰的展现链表结构的变化从而更容易构建起解题思路引入虚拟头结点哨兵位—便于处理很多边界情况题目给了特殊数据也不用怕空指针访问。而且方便我们对链表进行操作因为头节点的存在比如我们不用再分情况进行讨论而是一直在头节点后进行头插就行定义一个新的指针指向某个节点得以提前保存该节点当原本链表中指向它的指针断开后仍可找到它快慢双指针—判断带环链表、找环的入口、找链表中倒数第n个节点、链表中间节点二、两数相加Leetcode链接给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。解题思路由于数字的每位数是按链表逆序放置所以我们可以直接遍历两链表将遍历到的数字相加取结果个位数放入记录链表十位数为进位数。可以发现数字每位数逆序放置其实是比较友好的因为这和数学运算的顺序是一样的。代码实现及解析classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}classSolution{publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){ListNodecur1l1,cur2l2;//遍历两链表ListNodenewHeadnewListNode();//哨兵位ListNodetailnewHead;intsum0;while(cur1!null||cur2!null||sum!0){//注意这里的判断条件是或者if(cur1!null){sumcur1.val;cur1cur1.next;}if(cur2!null){sumcur2.val;cur2cur2.next;}ListNodenodenewListNode(sum%10);//取个位数放入节点sum/10;tail.nextnode;//尾插tailtail.next;}returnnewHead.next;}}总结复习解题思路三、两两交换链表中的节点Leetcode链接给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。对该题仅进行解题技巧总结总结这是链表很常见的题目就是要求我们对链表节点的位置进行更改/重排列链表我们通常的做法就是定义几个指针指向每次更改会影响到的几个节点防止它们因为指向断开而“丢了”然后依赖这几个指针对节点的指向进行更改再让这几个指针按规则移动往后遍历。就这样遍历完成节点的指向也均已正确更改我们在做这种“链表位置更改”的题目时无论是一次性更改还是分几段更改都建议使用“哨兵位”来连接每次更改后的一段新链表如果在原链表中直接操作会变非常复杂包括“反转链表”也建议使用哨兵位在哨兵位后面头插的方法方便且易懂我们面对类似链表“节点奇偶数”这样的问题时其实就是分类讨论看遍历到最后哪个指针会先为null此时可以以此来推断奇/偶数然后做出对应的处理四、重排链表Leetcode链接给定一个单链表 L 的头节点 head 单链表 L 表示为L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。解题思路根据链表排列的规则我们可以发现重排列的链表可以由两个链表合并而来。当把链表分为两半将左、右这两部分链表进行合并就可以得到目标链表。所以思路就清晰了我们可以分三步解题1.先找到链表的中间节点 2.再将右半部分反转 3.最后再将左、右两部分链表合并我们发现这三个步骤都是之前做过的题目找到链表的中间节点—快慢双指针把后面的部分逆序—三指针头插法合并两个链表—双指针至于链表节点个数奇、偶的问题前面已经讲过分情况来讨论。本题通过验证两种情况都可以让slow指针后面的链表归为右半部分并将其反转得到的结果链表一样代码实现及解析/** * 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; } * } */classSolution{publicvoidreorderList(ListNodehead){//1.找到链表的中间节点ListNodefasthead,slowhead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}//2.反转slow后面的链表ListNodenewHeadnewListNode();ListNodecurslow.next;ListNodecurNnull;while(cur!null){curNcur.next;cur.nextnewHead.next;newHead.nextcur;curcurN;}slow.nextnull;//将左半部分的链表与右半部分的链表断开//3.合并左、右两个链表ListNodeansHeadnewListNode();ListNodecur1head,cur2newHead.next;ListNodetailansHead;while(cur1!null){//本题中左半部分的链表较长所以一定是cur2先遍历完//先放左半部分链表的节点tail.nextcur1;cur1cur1.next;tailtail.next;//再放右半部分链表的节点if(cur2!null){tail.nextcur2;cur2cur2.next;tailtail.next;}}}}总结复习解题思路五、合并 K 个升序链表Leetcode链接给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。解题思路方法一合并两个有序链表已经做过那其实合并一堆有序链表的思路和合并两个的思路一致只不过后者是在两个节点中找出较小的而前者是在一堆节点中查找出最小的那个。而在一堆数据中不要求严格对其排序而要求每次找出最值并将其拿出这不就是优先级队列来干的事吗方法二使用专题七、八所介绍的分治思想解题思路很简单、代码框架也没变。代码实现及解析方法一使用优先级队列classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}classSolution{publicListNodemergeKLists(ListNode[]lists){//构建小根堆PriorityQueueListNodeheapnewPriorityQueue(newComparatorListNode(){publicintcompare(ListNodeo1,ListNodeo2){//这里compare方法的权限一定不能比父类小所以一定要加上public修饰returno1.val-o2.val;}});//先将每个链表的第一个节点放入堆中for(ListNodelist:lists){if(list!null)//链表不能为空heap.offer(list);}//再利用优先级队列的特性每次将较小的节点拿出尾插到newHead进行排序ListNodenewHeadnewListNode();ListNodetailnewHead;while(!heap.isEmpty()){ListNodetmpheap.poll();tail.nexttmp;if(tmp.next!null){heap.offer(tmp.next);//poll出节点后就要立即将该节点后面的节点offer入heap中}tailtail.next;}returnnewHead.next;}}方法二递归实现classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}classSolution{publicListNodemergeKLists(ListNode[]lists){returnmergeSort(lists,0,lists.length-1);}publicListNodemergeSort(ListNode[]lists,intbegin,intend){if(beginend)returnnull;if(beginend)returnlists[begin];intmidIndex(beginend)/2;ListNodel1mergeSort(lists,begin,midIndex);//合并左半部分ListNodel2mergeSort(lists,midIndex1,end);//合并右半部分//再合并l1、l2ListNodenewHeadnewListNode();ListNodecur1l1,cur2l2;ListNodetailnewHead;while(cur1!nullcur2!null){if(cur1.valcur2.val){tail.nextcur1;cur1cur1.next;tailtail.next;}else{tail.nextcur2;cur2cur2.next;tailtail.next;}}if(cur1!null)tail.nextcur1;elsetail.nextcur2;returnnewHead.next;}}总结复习解题思路六、K 个一组翻转链表Leetcode链接给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。解题思路又是一个“更改链表节点位置 ”题目我们依然使用“哨兵位” newHead 来接收翻转后的链表对原链表的节点进行每轮k个节点的多轮头插到新链表中。以上就是大体思路一个很重要的细节是cur在遍历原链表将节点头去插入新链表中后会回原链表以便下一次插入curNcur.next; … curcurN;这样的话下一轮再想去新链表 尾部进行头插的话就找不到新链表的尾部了因为cur已经回去了所以在此轮头插之前先保存下来此轮头插后的链表尾部其实就是第一个头插的节点头插的逻辑导致第一个节点会成为链表的尾部那么直接保存每轮翻转时头插时cur的初始值就行ListNode nextInsertPoscur;。代码实现及解析classSolution{publicListNodereverseKGroup(ListNodehead,intk){//先统计一下链表长度ListNodecurhead;intcount0;while(cur!null){count;curcur.next;}count/k;//统计完链表长度再以此计算需要翻转的次数//进行正式操作ListNodenewHeadnewListNode();ListNodetailnewHead;curhead;ListNodecurNcur.next;for(inti0;icount;i){//进行count轮翻转ListNodenextInsertPoscur;//记录链表的结尾也就是下轮翻转进行头插的位置头插所以第一个插入的节点是最后的末尾for(intj0;jk;j){//每轮翻转k个节点//头插k个节点curNcur.next;cur.nexttail.next;tail.nextcur;curcurN;}tailnextInsertPos;//更新下轮头插入位置}tail.nextcur;//最后再处理下原链表末尾不够k个一组的节点returnnewHead.next;}}总结复习解题思路尤其是第二段的细节处理这样的情况不常见