<Data Structures/Algorithms> leetcode hot100 - 141(142). Linked List Cycle

[LeetCode Hot 100] 141(142). Linked List Cycle

Problem Link

To detect a cycle in a linked list with O(1) space complexity, the Floyd’s Tortoise and Hare algorithm is used. A detailed explanation of Floyd’s algorithm can be found here.

Steps:

1. Initialize a fast pointer (fast) and a slow pointer (slow) at the head of the linked list.
2. Move fast two steps at a time, and slow one step at a time.
3. If fast reaches null, there is no cycle. If fast and slow meet, a cycle exists. Then proceed to step 4.
4. Move one pointer back to the head of the list while keeping the other at the meeting point.
5. Move both pointers one step at a time until they meet again. The meeting point is the entrance of the cycle.

Complete code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

中文原文

[LeetCode hot 100] 141(142). 环形链表

题目链接

环形链表的判断在要求空间复杂度为O(1)时，需要使用Floyd判圈法来判断是否存在环。Floyd判圈法的具体讲解看这里。

具体步骤为：

1. 快指针fast和慢指针slow指向链表头（首元结点）
2. fast每次移动两步，slow每次移动一步
3. 如果遇到null说明没有环，如果fast和slow相遇说明有环，进入4
4. 其中一个指针移回链表头，另一个不动
5. 两个指针每次移动一步，直到相遇，就是环的入口

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};