首页 > 代码库 > leetcode - Linked List Cycle

leetcode - Linked List Cycle

2024-07-09 17:04:42   218人阅读

题目：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?

 

个人思路：

1、判断一个链表是否有环，标准做法是采取快慢指针，一个走一步，一个走两步，当快指针追上慢指针时，表明有环

2、要注意几个地方，1、空节点链表无环 2、快指针的两步也是一步一步走的，每走一步都得进行检查

 

代码：

 1 #include <stddef.h> 2  3 struct ListNode 4 { 5     int val; 6     ListNode *next; 7     ListNode(int x) : val(x), next(NULL) {}; 8 }; 9 10 class Solution11 {12 public:13     bool hasCycle(ListNode *head)14     {15         if (!head)16         {17             return false;18         }19 20         ListNode *one = head;21         ListNode *two = head;22 23         while (true)24         {25             two = two->next;26             if (!two)27             {28                 return false;29             }30             if (two == one)31             {32                 return true;33             }34             two = two->next;35             if (!two)36             {37                 return false;38             }39             if (two == one)40             {41                 return true;42             }43             one = one->next;            44         }45     }46 };47 48 int main()49 {50     return 0;51 }
View Code

 

网上基本都是这种方法，主要问题是要考虑特殊情形和边界条件


联系
我们