102-帶環鏈表

給定一個鏈表，判斷它是否有環。

樣例

給出 -21->10->4->5, tail connects to node index 1，返回 true

挑戰

不要使用額外的空間

標簽

鏈表 兩根指針

思路

快慢指針的典型應用，使用塊指針 fast 與慢指針 slow，slow每次后移一位，fast 每次后移兩位，當fast 與 slow 指向同一節點時，說明存在環。就如同操場跑圈時，領先一圈的人會遇上跑在他后面的人那樣。

code

/*** Definition of ListNode* class ListNode {* public:* int val;* ListNode *next;* ListNode(int val) {* this->val = val;* this->next = NULL;* }* }*/ class Solution { public:/*** @param head: The first node of linked list.* @return: True if it has a cycle, or false*/bool hasCycle(ListNode *head) {// write your code hereListNode * fast = head, *slow = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if(fast == slow) {return true;}}return false;} };

轉載于:https://www.cnblogs.com/libaoquan/p/7168296.html

總結

以上是生活随笔為你收集整理的lintcode-102-带环链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。