判断链表是否带环

题目描述：

给定一个链表，判断链表中是否有环。

在这里插入图片描述

思路：

可以明确的是：若一个链表带环，那么用指针一直顺着链表遍历，最终会回到某个地方。
我们可以定义两个指针（快慢指针），两个指针均从表头开始同时遍历链表，快指针一次走两步，慢指针一次走一步。如果链表带环，那么快慢指针一定会相遇，否则快指针会先遍历完链表（遇到NULL）。

若是你不明白为什么链表带环，快慢指针就一定会相遇，那么你可以想想龟兔赛跑：
在这里插入图片描述

代码示例：

struct ListNode {int val;struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;//兔子走两步slow = slow->next;//乌龟走一步if (fast == slow)//兔子与乌龟相遇return true;}return false;
}

若链表带环找出环的入口

题目描述：

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

这不是一道简简单单的代码题，严格来说，这是一道数学推论题，若是不能得出最终推论，是不能很好的解决该问题的。

推论如下：

在这里插入图片描述

解释：

假设快指针走两步，慢指针走一步。头节点到入环结点距离为L，环入口结点到快慢指针相遇结点距离为X，环的长度为C。
当快慢指针相遇，快慢指针走的距离：慢指针：L+X 快指针：L+NC+X(N为快指针围着环走的圈数)
为什么有个N，假设环C很小，L很长，快指针可能在里面转了很多圈了。
然后就会有：2(L+X)=L+NC+X(2倍慢指针走的距离就是快指针走的距离，因为快指针走的步数时慢指针的两倍) 所以就有：
L+X=NC —> L=N*C-X
所以求环链表入环结点思路有：当快慢指针相遇时，让一个指针指向链表头，然后一起一个节点一个结点走，一定会在入口结点相遇。

代码示例：

struct ListNode {int val;struct ListNode *next;
};
struct ListNode *detectCycle(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)//相遇{struct ListNode* meet = fast;//相遇点while (head != meet){head = head->next;//一个指针从出发点开始走meet = meet->next;//一个指针从相遇点开始走}return meet;//两个指针相遇，返回当前结点}}return NULL;//链表不带环
}

其他高频的面试问题

问题一：为什么慢指针走一步，快指针走两步，他们一定会在环里面相遇？会不会永远追不上？请证明。

不会永远追不上，证明如下：
在这里插入图片描述

当快慢指针都进环了，假设快慢指针间的距离为N，当快慢指针走一步，他们之间的距离就缩短了1，再走一步就缩短了2…最后肯定他们之间的距离会缩短到0。

问题二：那么慢指针走一步，快指针走三步？走四步？或是走n步行不行？为什么？请证明。

不行，这样可能会追不上，证明如下：

在这里插入图片描述

解释：

假设快指针走3步，慢指针走1步。当快慢指针都进环后，假设快慢指针间的距离为N，环的周长是C，当快慢指针走一步，他们之间的距离就缩短了2，再走一步，快慢指针之间交开始的距离缩短了4。
分俩种情况：
1.若N为偶数，则他们之间的距离最终会减为0，即相遇。
2.若N为奇数，则他们之间的距离会减到1，然后减到-1，也就意味着他们之间的距离又变为了C-1，此时又分俩种情况：
1> 若C为奇数，则C-1为偶数，因为他们之间的距离一次缩小2，所有他们会相遇。
2> 若C为偶数，则C-1还是为奇数，也就是说他们之间的距离还是奇数，他们永远不会相遇。

当慢指针走一步，快指针走四步或是走n步时，证明过程类似，在此就不做赘述。