网络建站如何建成_搭建网站的企业_互联网营销案例分析_2023免费推广入口

141.判断链表是否带环

1. 这道题不能用比较链表中的值来判断是否带环，因为链表中不同节点的值可以相同，我们要比较地址来判断是否带环
2. 带环问题我们要用快慢指针来解决。让慢的指针一次走一步，快的指针一次走两步。这样如果链表中带环的话，慢指针一定会与快指针相遇。
3. 地址相同就是相遇，说明链表带环

把带环的链表想象成这个样子

bool hasCycle(struct ListNode *head) {struct ListNode *fast = head;struct ListNode *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){return true;}}return false;
}

142.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

这道题我们要找到他的入环点。

1.假设快指针fast在与慢指针slow第一次相遇时 fast只在环内多跑了一圈 （b+c）
那么在相遇点相遇时，slow跑了 a+b，fast跑了a+（b+c）+b。
又因为快指针一次走两步，慢指针一次走一步所以有：2（a+b）=a+2b+c
所以推出 a = c
所以我们相遇后只需要再定义一个指针 cur 从头节点位置开始走，slow从相遇点开始走，他们两相遇时就是链表中环的起始点

2.fast也可能在环内跑了很多圈才与slow相遇
但slow走的路程永远a+b

fast在环内走了很多圈后与slow相遇

fast走的时slow的二倍
同时去掉b>同时减去一个a

所以得处结论，我们可以用cur 指向头节点，让慢指针在环内与cur同时走最终还是会在入环点相遇，返回相遇点即可

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast = head;struct ListNode *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){struct ListNode *cur = head;while(1){if(cur == slow){return slow;}cur = cur->next;slow = slow->next;}}}return NULL;
}