vs怎么添加做网站,店标设计logo设计,做社交网站框架,杭州建设网页一.前言
今天在力扣上刷到一道链表题——环形链表https://leetcode.cn/problems/linked-list-cycle
想着和大家们分享一下。让我们直接开始今天的分享吧。、
二.正文
1.1题目描述 1.2题目分析
这道题是想让我们做出分析#xff0c;该链表是不是带环链表#xff0c;如果是…一.前言
今天在力扣上刷到一道链表题——环形链表https://leetcode.cn/problems/linked-list-cycle
想着和大家们分享一下。让我们直接开始今天的分享吧。、
二.正文
1.1题目描述 1.2题目分析
这道题是想让我们做出分析该链表是不是带环链表如果是带环链表就返回true。否则就返回false。
这道题我们可以采用快慢指针的办法定义一个快指针fast一次走两个节点。再定义一个慢指针slow一次只走一个节点。
如果不是带环链表slow在之后的遍历中是永远不可能与fast相遇的。因此当slow和fast相遇后就可以证明该链表是环形链表。这里咱们可以这样理解fast跑的快一些早早的就进入了环内当速度慢一些地slow进环以后fast可能已经循环了好几圈了。此时就变成了fast追击slow的问题了。
为什么我们在这里肯定fast与slow一定相遇呢。
这里我们可以做一个假设假设当slow刚进入环的时候fast与slow的距离为N。
slow走一步。fast走两步。它们的距离就会有以下变化
N
N-1
N-2
N-3
。。。。
N-n
因此一定存在某个瞬间N-n为0。即两个指针相遇。 那么如果fast一次走三步fast和slow会相遇吗 同理fast走4步也是按此分析。
1.3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {if(headNULL)return false;
ListNode* slow,*fast;
slowfasthead;
while(fastfast-next){fastfast-next-next;
slowslow-next;
if(fastslow)
{return true;
}}return false;
} 三.结言
题目分享写到这就结束了。帅哥美女们觉得对自己有所帮助能不能给我个三连。谢谢啦。
