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是否为空,避免对空指针操作
寻找环的入口:
此处x为head到入口的距离,y为入环到相遇点的距离,z为相遇点到入环的距离。因此可知,构建两个节点分别位于head和相遇点,以同样速度前进,此时的相遇点为入口。