首页 > 代码库 > [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?
思路：快慢指针的应用。快慢指针指的是移动的步长，即每次向前移动的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。
如果快指针到达NULL,说明链表以NULL为结尾，没有环。如果快指针追上慢指针，则表示有环。
时间复杂度O(n),空间复杂度O(1)
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 bool hasCycle(ListNode *head) {12 if (head == NULL) return head;13 14 ListNode *slow = head, *fast = head;15 while (fast != NULL && fast->next != NULL) {16 fast = fast->next->next;17 slow = slow->next;18 if (fast == slow) return true;19 }20 21 return false;22 }23 };
[LeetCode] Linked List Cycle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。