[Lc]142环形链表II

题目

链表定义：

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

题解

141的进阶

1. 快慢指针法

设环长度为c，环前端长度为a，相遇点到环前端长度为y
快指针在一圈内必追上慢指针，即快指针只比慢指针多走一圈
设环前长度为a，环长为c，相遇点距环起点为y
$(a+y)/1 = (a+c+y)/2$
$a = c-y$
即环剩的长度与环前长度相等

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

class Solution {//#141的进阶
public:
    ListNode *detectCycle(ListNode *head) {//两种方法。1、两指针法，数学计算得出规律
        ListNode *slow = head, *fast = head;//创建双指针
        while(fast && fast->next){//当fast为空或fast下一位为空，停止遍历，注意判断fast要在前
            slow = slow->next;//慢指针走一步
            fast = fast->next->next;//快指针走两步
            if(slow == fast) break;//当快指针追上慢指针，跳出循环
        }
        if(!fast || !fast->next) return NULL;//若fast指针为空，或者fast一位为空，返回null
        fast = head;//将fast移回首位
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;//这时一个指针走一步，直到相遇，相遇点就是环起始点
        }
        return fast;        
    }
};

2. 列表存值法

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {//两种方法。2、列表存值法，使用额外空间了
        unordered_set<ListNode*> m;//设置无续set存值
        ListNode *cur = head;//设置指针指向链表头
        while(cur){//当指针指向的值存在时
            if(m.count(cur)) return cur;//若set里有这个值，说明绕回来了，返回当前指针
            m.insert(cur);//否则在set里插入指针当前节点
            cur = cur->next;//后移指针
        }
        return NULL;//若跳出循环，则返回NULL
        
    }
};