前端做网站需要,北京网站建设建站,中交路桥建设有限公司待遇,刷赞网站推广qq目录 1. 环形链表||#xff08;142#xff09;1.1 题目描述1.2 题目分析1.3 代码 2. 环形链表#xff08;141#xff09;2.1 题目描述2.2 题目分析2.3 代码 1. 环形链表||#xff08;142#xff09;
1.1 题目描述 1.2 题目分析
带环链表#xff1a;尾节点的next指向链… 目录 1. 环形链表||1421.1 题目描述1.2 题目分析1.3 代码 2. 环形链表1412.1 题目描述2.2 题目分析2.3 代码 1. 环形链表||142
1.1 题目描述 1.2 题目分析
带环链表尾节点的next指向链表中的任意节点。 那么环形链表怎么判断链表带不带环 得考虑哪个节点是环里面的。 我们就会想到如果一个节点位置出现两次那么就是进环了。但是并不能知道怎么判断位置重复出现。什么时候进环又不知道。
这里用快慢指针最合适。 当两个指针都进入环以后slow开始追击fast到某一个位置会相遇。 只有两个指针都进入环才会相遇。 假设将起点到入环口点距离记为L入口点到相遇点的位置记为X环的长度记为C。 从开始位置相遇时slow走的距离是LX从开始点相遇时到fast走的距离是Ln*CX。因为不知道在slow进环之前,fast已经在环里转了多少圈了就设为n。 结论一个指针从相遇点开始走一个指针从头开始它们会在入口点相遇。
1.3 代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *slow,*fast;slowfasthead;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){struct ListNode *meetslow;while(head!meet){headhead-next;meetmeet-next;}return meet;}}return NULL;
}2. 环形链表141
2.1 题目描述 2.2 题目分析
与上一题类似也使用快慢指针不同的是这里不需要找出相遇点的位置只需要判断是不是有环就行。 如果slow走一步fast走2步一定会相遇为什么呢 slow进环后fast和slow的距离每次追击都会缩减1。 假设slow进环时fast与slow之间的距离为N。 如果slow一次走一步fast一次走3步一定会相遇吗 此时距离变化就是这里就得分情况了 总之;
如果N是偶数直接就追上了。如果N是奇数C是偶数永远追不上。如果N是奇数C是奇数第一轮错过了第二轮就追上了。 如果slow一次走n步fast一次走m步一定会相遇吗(mn1) 这时缩小的距离是m-n,如果满足N%(m-n)0就能追上。
2.3 代码
bool hasCycle(struct ListNode *head) {struct ListNode *slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
}有问题请指出大家一起进步
