代码随想录训练营Day4:24两两交换链表中的节点、19删除链表中倒数第n个节点、链表相交、142环形链表II

发布于:2022-12-08 ⋅ 阅读:(727) ⋅ 点赞:(0)

1.两两交换链表中的节点代码随想录 (programmercarl.com)

 

        1.此题最重要的便是搞清楚循环终止的情况,若链表节点数为奇数,则cur->next->next为空时循环结束,若链表节点数为偶数,则cur->next为空时循环结束,(可以自己找例子试一试)并且while循环中二者的顺序不能弄反,若弄反了则会引发空指针异常。

        2.操作的指针一定要指向将要反转的两个节点的前一个节点。

        此题刷题中的错误:无,但是1非常值得关注,之前刷题的时候根本没注意,稀里糊涂就过了 ,也不知道原因。

2.删除链表中倒数第n个节点:代码随想录 (programmercarl.com)

        1.本题最主要要学的思想就是如何找到倒数第n个节点,本题的法是利用双指针,设置快慢指针的初始位置都在dummynode。先让快指针走n步,然后快慢指针一起出发,直到快指针为空,此时慢指针也到达了倒数第个节点。(可以举例自己实验一下)

        2.一定记住,每当要删除链表中的节点的时候,要处理的一定是被删除节点的前一个节点。故我们快指针要先走n+1步,使得慢指针最终停在倒数第n+1个节点。

        3.为了防止空指针的出现可以再第一个while循环之前就n++,省去代码中fast = fast->next的操作。

        4.一个小总结:在链表中如果想要指针移动n步,直接while(n--)就行。

 3.面试题 02.07. 链表相交:代码随想录 (programmercarl.com)​​​​​

 

        1.要从此题学会求链表长度的方法,如上图代码。

        2.注意求完链表长度之后,要及时将cura、curb重置为heada和headb,以便于后续的操作。 

        3.手动确定两条链表哪个长度更大,以便后续操作。

        4.学会最后一步的操作。

        5.最后的判别条件为两个节点本身是否相同而不是两个节点的值是否相同。

        刷题过程中遇到的错误:5.   

4.环形链表II:代码随想录 (programmercarl.com)

 

        1.fast和slow一定会相遇的原理:可以理解为fast在后面追slow,每次离她更近一步,一步一步总会追上的,但要是fast心机了,slow走一步,fast走三步,那此时fast相当于一次靠近slow两步,很有可能他们就错过了(可以自己模拟一下)所以心急吃不了热豆腐。

        2.fast的判断条件为何是fast=null&&fast->next != null ?因为fast要走两步,所以要这么判断。

        3.为何卡哥说当n>1时和n=1时是一样的?因为可以理解成某个指针在f和s相遇处又走了n-1圈,再走z的距离和从head出发的指针在出口处相遇,这个要是再忘了可以看卡哥视频模拟讲解,一目了然。

今日总结:今天大概花了三四个小时,时间还是挺多的,要合理安排好时间。

 

 

 

 

 

 

 

 

本文含有隐藏内容,请 开通VIP 后查看