leetcode-141-142

141. 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?

---

题意理解

给定一个链表，判断链表中是否有环。不要有额外的空间消耗。

---

解法思路

双指针法：

最常用的方法，快慢指针，慢指针每次移动一步，快指针一次移动两步。如果链表中没有环，那么快指针将先到达链表结尾，并且指向 NULL；如果链表中有环，则快指针会在环中循环，直到慢指针进入环中，快指针将会追上慢指针，两者相等。

代码如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast->next != NULL && fast->next->next != NULL) {
            if (slow == fast)
                return true;
            slow = slow->next;
            fast = fast->next->next;
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：O(N)。如果链表中无环，则在快指针到达链表结尾时经过 N/2 步左右，所以复杂度为 O(N)；如果链表中有环，则最坏情况下，当慢指针几乎绕环一圈时快指针才追上它，所以是 N 步左右，所以复杂度为 O(N)。综上，时间复杂度为 O(N)。
• 空间复杂度：O(1)。只使用了两个指针。

---

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

---

题意理解

给定一个链表，如果链表中有环，返回环开始的节点；如果没有环，则返回 null。并且不能修改这个链表。

---

解法思路

和上面那题一样，都是使用双指针法，但是要输出环开始的节点需要一些其他的计算。

假设经过 k 步，快慢指针相遇；假设环的长度是 r；所以有：2k - k = nr，即 k = nr （其中n表示快指针在环中循环的次数）。

假设链表表头到环的起点的距离为 s；假设环的起点到快慢指针相遇的节点的距离为 m；所以有：s = k - m。

s = nr - m = (n - 1) + (r - m)，n = 1,2,3,...

所以，可以再使用两个指针，慢指针从链表表头开始，每次移动一步；快指针从快慢指针相遇的节点开始，每次也移动一步，那么经过 s 步之后，快慢指针将会在环的起点相遇。

代码如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL &&fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast){
                slow = head;
                fast = fast;
                while (slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }           
        }
        return NULL;
    }
};

复杂度和上一题一样，都为 O(N).

---