【数据结构经典面试题】是否形成有环链表

1.环形链表oj

2. oj解法

利用快慢指针：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow = head, *fast = head;
    
    while(fast && fast -> next)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.面试加问

当然面试题不会这么容易，面试官随之抛下以下两个问题：
1.有没有可能快慢指针永远无法相遇呢？
2.如果快指针一次走3步，一次走4步，一次走n步还会不会相遇呢？

经过简单思考可以得出：当快指针一次走两步时，快慢指针每次行动的间隔值为1，那么此时当慢指针进入圆环开始被快指针追击时，必定会被追上。

那么如果快指针一次走三步呢?

有没有可能慢指针和快指针永远无法相遇呢?
这里进行简单的数学证明：

简单画图分析：
设链表从开始到进入环的长度为L，两指针在距换开始点的N的长度相遇，环长为C。
从中可以得到哪些数学的等量关系式呢？
已知快指针的速度是慢指针的三倍，那么其走的路程也就是三倍，也就是每次追击两者之间的距离减少2

这里给出简单的思路图：

从图中可以看出

从图中可以看出当初始的N值为奇数时，且环长C为偶数时，两指针永远无法相遇。
那么现在就是要判断此种情况是否存在。

可推出此等式，从中我们可以发现，=左边为2L，永远为偶数，而右边为一个减式。
通过数学知识，我们得知当两数相减时，只有偶数-偶数或者奇数-奇数时得到偶数，所以当C为偶数时，（x+1）*C为偶数，此时N也为偶数，那么之前讨论的永远无法追上就时谬论了。
因此在进行第二轮追击时就可以追上，从而解得此题。

以及后面的快指针为4步N步都是同一解法。

如果被面试的是你，你答得出来吗？面试官先抛出一个简单代码题，随之考察面试者的数理分析能力，所以数学基础也是不可或缺的。

感谢大家的阅读，我将持续更新经典面试题。