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;
}
3.面试加问
当然面试题不会这么容易,面试官随之抛下以下两个问题:
1.有没有可能快慢指针永远无法相遇呢?
2.如果快指针一次走3步,一次走4步,一次走n步还会不会相遇呢?
经过简单思考可以得出:当快指针一次走两步时,快慢指针每次行动的间隔值为1,那么此时当慢指针进入圆环开始被快指针追击时,必定会被追上。
那么如果快指针一次走三步呢?
有没有可能慢指针和快指针永远无法相遇呢?
这里进行简单的数学证明:
简单画图分析:
设链表从开始到进入环的长度为L,两指针在距换开始点的N的长度相遇,环长为C。
从中可以得到哪些数学的等量关系式呢?
已知快指针的速度是慢指针的三倍,那么其走的路程也就是三倍,也就是每次追击两者之间的距离减少2这里给出简单的思路图:
从图中可以看出
从图中可以看出当初始的N值为奇数时,且环长C为偶数时,两指针永远无法相遇。
那么现在就是要判断此种情况是否存在。
可推出此等式,从中我们可以发现,=左边为2L,永远为偶数,而右边为一个减式。
通过数学知识,我们得知当两数相减时,只有偶数-偶数或者奇数-奇数时得到偶数,所以当C为偶数时,(x+1)*C为偶数,此时N也为偶数,那么之前讨论的永远无法追上就时谬论了。
因此在进行第二轮追击时就可以追上,从而解得此题。
以及后面的快指针为4步N步都是同一解法。
如果被面试的是你,你答得出来吗?面试官先抛出一个简单代码提,随之考察面试者的数理分析能力,所以数学基础也是不可或缺的。
感谢大家的阅读,我将持续更新经典面试题。