首页 > 代码库 > 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指针一起循环之前,需要额外判断一下