首页 > 代码库 > LeetCode[Linked List]: Linked List Cycle
LeetCode[Linked List]: 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?
这个题目如果没有空间复杂度O(1)的限制,我可以想到的方法就是:遍历整个list,将每个节点的地址存入一个vector,如果发现某个节点的next的地址已经在vector中,那么必然存在cycle。
由于空间复杂度O(1)的限制,我没有想出解决问题的办法,在Discuss上学到了一个非常巧妙的方法:
设置两个指针,一个指针每一次走一步,另外一个指针每次走两步,如果存在环的话,快指针必然会赶上慢指针。
实现代码也非常简单:
bool hasCycle(ListNode *head) { if (!head) return false; ListNode *slow = head, *fast = head; while (slow->next && fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; }
LeetCode[Linked List]: Linked List Cycle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。