目录
1.铺垫-----带环链表基本了解
2. 题目:环形链表
3.环形链表||
编辑 3.1题解1
3.2 题解2
4.总结
1.铺垫-----带环链表基本了解
环形链表题目启迪:
环形链表特点:遍历链表会出现一模一样的地址
2. 题目:环形链表
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/linked-list-cycle/
启迪:
首先,如果是循环链表这种特殊的带环指针,那么当我们用一个指针来遍历这个链表,就会有遍历指针等于头节点停下来,就判断有环存在。
那么对于其他带环链表来说,无法判断在哪一个节点开始是环的开始节点,如何找得到两个相等的指针呢。
这里使用快慢指针的思想,既定义两个指针,如上图所表现,最终两个指针都会进入我们的环形链表中,不断的跑,如果两者的速度差控制合适,那么总有一瞬间两者就会相遇,当两者相遇就可以说明这个链表带环。那么关键在于快慢指针之间的速度差该设置为多少。
首先,我们可以猜想快指针的速度是慢指针速度的两倍,就是说慢指针一次走一步,快指针一次走两步:
那么当我们的慢指针进入环时,如果两者目前没有相遇,那么是不是应该是快指针在追击慢指针,设慢指针刚入环时他们之间的距离为N
如果速度是三倍,同样的分析:
当慢指针进入环时:设两者的距离为N,那么每走一次,快指针走三步,慢指针走一步,二者之间距离减少2;
N-2 N-4 N-6 N-8
如果N是偶数,最后就可以追上
如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1
每移动一次距离-2,
设c-1为N
N-2 N-4 N-6 N-8.............
如果N是偶数,最后就可以追上
如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1
那么如果c-1是奇数,就会追不上了。
解题代码:
bool hasCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true; }}return false;}
3.环形链表||
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/linked-list-cycle-ii/
3.1题解1
结论:从相遇点定义一个指针,在头结点出发一个指针,两个指针速率相同,最后会在环的入点相遇
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走while(meet != cur){cur = cur->next;meet = meet->next;}return cur;}}return NULL;}
3.2 题解2
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * cura = headA,*curb = headB;int lena = 1;int lenb = 1;while(cura->next){cura = cura->next;lena++;//计算链表a的长度}while(curb->next){curb = curb->next;lenb++;//计算链表b的长度}//如果两个链表相交,那么尾结点的地址一定相等//所以这里就可以判断一下两个链表是否相交if(cura != curb){return NULL;}int gap = abs(lena-lenb);//计算两个链表之间的差值,用来绝对值struct ListNode*longst = headA,*shortlist = headB;if(lena<lenb){longst = headB;shortlist = headA;}while(gap--){longst = longst->next;//长的先走差距步}//同时找交点while(longst != shortlist){longst = longst->next;shortlist = shortlist->next;}return longst;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走struct ListNode * newnode = meet->next;meet->next = NULL;return getIntersectionNode(head,newnode);}}return NULL;}
4.总结
带环链表的题目涉及到数学分析,从解题的过程中我们也能感知到,可以结合图解多看一下代码,结合理解。以上就是本期的所有内容,知识含量蛮多,大家可以配合解释和原码运行理解。创作不易,大家如果觉得还可以的话,欢迎大家三连,有问题的地方欢迎大家指正,一起交流学习,一起成长,我是Nicn,正在c++方向前行的奋斗者,数据结构内容持续更新中,感谢大家的关注与喜欢。