代码随想录第四天|24.两两交换链表节点、19.删除链表的倒数第N个节点、面试02.07. 链表相交、142.环形链表

24.两两交换链表节点

卡在了循环的边界条件上

看视频后:

建立虚拟头节点,三个节点为一组操作节点交换,用cur和cur->next以及cur->next->next.

边界条件为while(cur->next!=NULL&cur->next->next!=NULL)

视频中建立了两个temp指针存放1和3号位,但实际上只需要存放3号位即可(就是next写的比较多)



19.删除链表的倒数第N个节点

构建了虚拟头节点,先遍历了链表找到了链表长度,然后i-n得到正方向的第N个节点,然后正常删除节点即可。时间复杂度为O(2n)即O(N)

看视频后:

构建虚拟头节点,建立快慢指针。快指针先走n步,然后在while(quick->next!=NULL)的循环内快慢指针一起走,slow停在删除的节点前一个节点,然后删除节点即可。


面试02.07. 链表相交

思路:

暴力遍历两个链表寻找地址相同的节点。debug的时候发现忘记重制cur2=headB了导致一直出错。

看代码后:

因为不存在环形,则链表相交后的节点是相同的。所以可以找两个链表的长度,将链表尾对齐,把长链表的cur移动到和短链表首相同的位置,然后再逐个对比后面节点。


142.环形链表

思路:

此题无思路。

看视频后:

环形链表分为两个问题:是否有环和寻找环的入口。

是否有环:通过快慢指针进行判断,快指针移动两步,慢指针移动一步,看是否会相遇

记得判断fast和fast->next是否为空,避免对空指针操作

寻找环的入口:

2(x+y)=x+y+n(y+z)

x=(n-1)(y+z)+z

此处x为head到入口的距离,y为入环到相遇点的距离,z为相遇点到入环的距离。因此可知,构建两个节点分别位于head和相遇点,以同样速度前进,此时的相遇点为入口。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容