首页 > 代码库 > Leetcode:Linked List Cycle 链表是否存在环
Leetcode:Linked List Cycle 链表是否存在环
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?
解题分析:
大致思想就是设置两个指针,一个指针每次走两步,一个指针每次走一步,如果这两个指针碰头了,那么一定就存在环
可以类比两个人在环形操场跑步,同时出发,一个跑得快,一个跑得慢,如果跑得快的人追上跑得慢的人,那么跑得快的人相当于多跑了一整圈
wiki:http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
class Solution { public: bool hasCycle(ListNode *head) { if (head == nullptr) return false; if (head->next == nullptr) return false; ListNode* fast = head; ListNode* slow = head; while (fast != nullptr && fast->next != nullptr && slow != nullptr ) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return true; } } return false; } };
每个指针都需要判断为空情况
Linked List Cycle II:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
解题分析:
在上题中,slow指针和fast指针如果碰头了,那么链表中一定存在环
在快慢指针碰头的那一刻,我们另外设置一个新指针start,start指针和slow指针每次循环都前进一步,这两个指针一定会在环的开始处相遇
class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; if (head->next == nullptr) return nullptr; ListNode* fast = head; ListNode* slow = head; ListNode* start = head; while (fast != nullptr && fast->next != nullptr && slow != nullptr) { fast = fast->next->next; slow = slow->next; if (fast == slow) { break; } } if (slow == start) return start; while (slow != nullptr && start != nullptr) { slow = slow->next; start = start->next; if (slow == start) { return start; } } return nullptr; } };
注意:存在一种情况就是 slow指针和fast指针恰好在链表开头相遇了,所以在 slow和start指针一起循环之前,需要额外判断一下
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。