环形链表II

前两天一直在debug，今天才有时间好好刷一下力扣，今天在代码随想录上看到环形链表，链接如下：https://leetcode.cn/problems/linked-list-cycle-ii/description/

这道题官方有两种解法，一种是相对比较简单的哈希表，还有一种是利用数学计算出他们的规律进而解题。
首先说第二种，在示例中

      3 -> 2 -> 0-> 4->
	   ^            |
	   <- <- <-  <-

链表从3开始，依次对2 0 4 2 0 4进行遍历。如果无环返回null，有环的话求他们的环起始点。本质上这是两个问题，所以先对第一个问题求解：判断是否有环。在这里我们先设置两个指针，也就是双指针法(fast/low)，然后我们fast指针每次遍历两个结点，low指针每次遍历一个结点，那么最后他们一定在环中相遇。

而后计算他们在入环中的第一个入环结点，这个我是直接看的答案，想了一会一点思路没有果断放弃 :-<(妈的看答案还得反应半天)
简单来说：设从起始结点到环起始点的距离为x，环起始点到他们在环中相遇的结点距离是y，相遇的点要走z个结点回到环起始点，具体的图如下：

那么从这图中和我们之前设置可知，slow指针共走了x+y个结点，fast指针共走了x+y+n(y+z)个结点。由于fast和slow是二倍的关系，所以可以列等式

(x + y) * 2 = x + y + n ( y + z ) 
 x = (n - 1)(x + y) + z

n是fast在相遇前走过的圈数。然后进行化简得到第二行，这里n是需要大于等于1的，因为fast指针必须至少转1圈，否则就出现没转一圈直接和slow相遇了（这不符合常理！）综上，当n = 1时，x = z。也就是一个结点从相遇的点开始出发，另一个点从头结点开始出发，走相同的距离然后相遇。起始n不等于1也是一样，只是在环中的结点要多走几圈罢了。代码实现如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if((head == nullptr) || (head->next == nullptr)){
            return nullptr;
        }
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        do{
            int count = 0;
            while((count != 2)&&(fast != NULL)){
                fast = fast->next;
                count++;
            }
            slow = slow->next;
        }
        while((fast != slow)&&(slow != nullptr));
        struct ListNode* q = fast;
        struct ListNode* p = head;
        while((p!=NULL)&&(q!=NULL)){
            if(p == q){
                return p;                
            }
            p = p->next;
            q = q->next;
        }
        return nullptr;
    }
};

代码写的过于冗余，但是还是可以看懂的。
同时还有一种方法是哈希表，虽然数据结构学过哈希表，但是并没有在C++中用过，所以写的不太熟练。
如果用哈希表的话那么就会简单很多了，下面是详细解释官方题解(因为没怎么用过)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 定义一个哈希表用于存储访问过的节点
        unordered_set<ListNode *> visited;
        
        // 遍历链表
        while (head != nullptr) {
            // 如果当前节点已经在哈希表中，说明遇到了环
            if (visited.count(head)) {
                return head; // 返回环的起点
            }
            // 将当前节点加入哈希表
            visited.insert(head);
            // 移动到下一个节点
            head = head->next;
        }
        
        // 如果没有遇到环，返回 nullptr
        return nullptr;
    }
};

unordered_set<ListNode > visited;
//无序集合来存链表中的结点指针，集合中每个元素都是ListNode的指针
然后需要遍历链表，每个结点在哈希表中貌似都是head结点

if (visited.count(head)) {     //使用visited.count(head)检查当前结点是否在集合中，
    return head;		//如果返回1就代表访问过了，就代表我们遇到环了，
}			       //当前结点就是环起点。

visited.insert(head); 当前结点没访问过的话，就把此结点添加到集合中，同时移动到下个结点head = head->next;