《leetCode》：Linked List Cycle

本文主要是介绍《leetCode》：Linked List Cycle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given a linked list, determine if it has a cycle in it.Follow up:
Can you solve it without using extra space?

题目大意：不能用额外的空间来判断一个链表是否有环。

思路

如果一个链表存在环，当我遍历这个链表时，将我们遍历过的每个节点进行标记，如果被标记的节点又被遍历到的时候就出现了环，基于这样的一个思路就开始写代码，但是问题来了，应该用什么特殊的值来进行标记呢？？？没有发现，于是发现这个根本就行不通，但是自己还是试了下，用-1000000000作为标记，如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {if(head==NULL){return false;}struct ListNode *cur=head;struct ListNode *next=head;while(cur->next!=NULL){if(cur->val!=-1000000000){//设置一个标志位 cur->val=-1000000000;}else{return true;}cur=cur->next; }return false;
}

由于是自己随便选的一个数作为节点遍历过的标记，原以为肯定不能AC，发现居然AC了也，只能说这个测试平台还需要完善。
AC结果如下：

虽然上面的代码AC了，但是自己知道此题的考点并不在此，因此，自己将会继续思考。

思路二

思路:用两个指针来进行遍历即可 ,一个只移动一个节点，一个移动两个节点 ；如果一前一后的节点最终指向了同一个节点，则说明有环，否则无环。

实现代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {if(head==NULL||head->next==NULL){//没有节点和只有一个节点不会出现环 return false;}struct ListNode *oneStep=head;struct ListNode *twoStep=head->next; while(oneStep!=twoStep){if(twoStep==NULL||oneStep==NULL||twoStep->next==NULL) return false;else{oneStep=oneStep->next;twoStep=twoStep->next->next;}}//如果oneStep和twoStep指针指向了同一个节点，则必定有环return true; }

这篇关于《leetCode》：Linked List Cycle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---