相册网站怎么做的,wordpress安装md,工程建设信息官方网站,潍坊网站制作价格T04BF #x1f44b;专栏: 算法|JAVA|MySQL|C语言 #x1faf5; 小比特 大梦想 此篇文章与大家分享链表专题的第一部分 如果有不足的或者错误的请您指出! 1.链表常用技巧总结
1.1引入虚拟头结点
在力扣上,基本提供的链表题目都是无头的,但是针对无头链表,我们最… T04BF 专栏: 算法|JAVA|MySQL|C语言 小比特 大梦想 此篇文章与大家分享链表专题的第一部分 如果有不足的或者错误的请您指出! 1.链表常用技巧总结
1.1引入虚拟头结点
在力扣上,基本提供的链表题目都是无头的,但是针对无头链表,我们最怕的就是参数链表是一个空链表,就容易出现对null的访问.当我们引入虚拟头结点后,我们并不关心这个头结点里面放的是什么值,而这个节点只是起到一个哨兵的左右 举一个例子,如果我们要合并两个链表,引入第三链表将两个链表合并 在没有引入虚拟头结点的情况下: 那么我们的第三个链表就要先判断是否已经有节点了??如果有,直接插在后面即可;如果没有就要将插入的节点作为头结点 但是如果我们引入虚拟头结点 此时我们就不需要判断了,只需要将两个链表的节点依次插入到newHead后面即可 引入虚拟头结点的优势还有很多,我们在后面的题目中更能感受到
1.2不要吝啬空间
在链表专题,如果我们吝啬空间,有时候会给我们带来很大麻烦 举个例子: 我们通常会做到这样一种题目:在prve和prev.next节点之间插入cur节点 我们通常会这样做: ①cur.next prev.next ②prev.next.prev cur ③prev.next cur ④cur.prev prev 这四步操作中,前两步是一定要在后两个之前的 但是如果我们直接将prev.next用用一个临时节点存储起来: 这是就没必要去担心什么顺序问题了,直接针对三个节点进行操作即可
1.3快慢双指针的利用
快慢双指针在链表操作中经常遇到,而最常用的是我们下面这三种操作,最重要的是这三种操作往往只是作为一道题目里面的一小部分存在
1.3.1判断链表是否有环
题目:判断链表是否有环 在这道题中,我们定义一个fast指针和slow指针,fast指针一次走两步,slow指针一次走两步,那么如果链表没环,那么fast指针一定会走到null,如果链表没环,那么fast指针和slow指针一定会在环的某一点相遇 代码呈现:
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if(fast slow){return true;}}return false;}
}1.3.2找到链表环的入口
题目:找到环的入口 在上一题的基础上,如果链表有环,我们需要找到环的入口 实际上这道题有一个数学推导出来的结论:在fast指针和slow指针相遇点,此时这个相遇点距离环的入口,与起跑点距离环的入口,距离是一样的 即蓝色路程和红色路程是一样的 那么我们再定义一个节点node在起跑点位置,slow和node同时移动,二者相遇点就是环的入口 代码呈现:
public class Solution {private ListNode isCircle(ListNode head){ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if(fast slow){return slow;}}return null;}public ListNode detectCycle(ListNode head) {ListNode node isCircle(head);if(node null || node.next null){return null;}ListNode cur head;while(cur ! node){cur cur.next;node node.next;}return cur;}
}1.3.3删除链表的倒数第k个节点
同样利用双指针,我们让fast指针先走k步,此时fast和slow之间的距离就是k;接着让fast和slow指针同时走,直到fast为null,此时slow和空节点的距离就是k,即为倒数第k个节点 代码呈现:
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(head null || head.next null){return null;}ListNode node new ListNode(-1,head);//解决头结点被删的情况ListNode fast node;ListNode slow node;while(n 0){n--;fast fast.next;}while(fast.next ! null){fast fast.next;slow slow.next;}slow.next slow.next.next;return node.next;}
}1.3.4寻找中间节点
题目:链表的中间节点 固定套路:定义fast指针和slow指针,fast一次走两步,slow一次走一步,当fast为空或者fast.next 为空时,slow所在位置就是中间节点的位置 代码:
class Solution {public ListNode middleNode(ListNode head) {ListNode fast head.next;ListNode slow head;while(fast ! null){if(fast.next ! null){fast fast.next.next;}else{fast fast.next;}slow slow.next;}return slow;}
}1.4反转链表
题目:反转链表 这道题如果引入虚拟头结点,那么在时间复杂度为O(n)的情况下就能完成 即直接往虚拟头结点后面进行头插即可
class Solution {public ListNode reverseList(ListNode head) {ListNode newHead new ListNode(0);ListNode cur head;while(cur ! null){ListNode tmp cur.next;cur.next newHead.next;newHead.next cur;cur tmp;}return newHead.next;}
}2.两数相加
题目:两数相加
2.1解析
思路比较简单,用两个指针遍历两个链表,每次将两个节点里面的值相加,将得到的数的个位数作为新节点的值,把新节点插入到引入的虚拟头结点,同时记录下此时两数相加的进位,在下次计算的时候要加上进位
2.2题解
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 l1;ListNode cur2 l2;int tmp 0;ListNode newHead new ListNode(0);ListNode cur newHead;//记录新链表的最后一个节点while(cur1 ! null || cur2 ! null || tmp ! 0){//tmp ! 0 是为了解决最后计算完还有进位的情况if(cur1 ! null){tmp cur1.val;cur1 cur1.next;}if(cur2 ! null){tmp cur2.val;cur2 cur2.next;}ListNode node new ListNode(tmp % 10);tmp / 10;cur.next node;cur cur.next;}return newHead.next;}
}3.两两交换链表中的节点
题目:两两交换链表中的节点
3.1解析
这道题就能体现出我们之前说过的不要吝啬变量的好处 为了方便,我们还是引入虚拟头节点 对此链表进行两两翻转操作 要翻转两个节点,不仅需要记录这两个节点,还要记录前一个节点和后一个节点 因此我们直接引入这些变量: 就是对cur和next进行翻转操作,就很简单明了了,直接让prev.next next; next.next cur; cur.next nnext; 此时前两个就翻转完了 接下来就要让prev指向当前cur的位置,继续进行刚才的操作 那么循环什么时候结束呢??会有两种情况 (1)就像我们上面这一组一样,当我们再次把prev指向cur的时候 此时,没翻转的节点就一个,那么就不用翻转了,即当next null的时候是循环结束 (2)假设我们没有最后一个节点 那么此时已经没有节点了,自然就不需要翻转.因此cur null也是循环结束的标志
3.2题解
class Solution {public ListNode swapPairs(ListNode head) {if(head null || head.next null){return head;}ListNode newHead new ListNode(0,head);ListNode prev newHead;ListNode cur prev.next;ListNode next cur.next;ListNode nnext next.next;while(cur ! null next ! null){prev.next next;next.next cur;cur.next nnext;prev cur;cur prev.next;if(cur ! null){next cur.next;if(next ! null){nnext next.next;}}}return newHead.next;}
}4.重排链表
题目:重排链表
4.1解析
此题最简单的思路就是将数组划分为两部分,并将右边的部分逆置,随后依次插入新的链表中 而其中的操作就是寻找中间节点、链表逆置、合并链表我们在一开始都是讲过的因此我们直接代码呈现\
4.2 private ListNode findCenter(ListNode head){ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;}return slow;}private ListNode reverse(ListNode head){ListNode newHead new ListNode(1);ListNode cur head;while(cur ! null){ListNode tmp cur.next;cur.next newHead.next;newHead.next cur;cur tmp;}return newHead.next;}public void reorderList(ListNode head) {ListNode center findCenter(head);ListNode node reverse(center.next);//让中心节点的后面部分逆置center.next null;//断开两部分ListNode cur1 head;//遍历前一部分ListNode newHead new ListNode(0);ListNode cur newHead;//遍历新链表//合并while(cur1 ! null){//前面的部分一定比后面的部分长cur.next cur1;cur1 cur1.next;cur cur.next;if(node ! null){cur.next node;node node.next;cur cur.next;}}head newHead.next;}感谢您的访问!!期待您的关注!!! T04BF 小比特 大梦想
