判断给定的链表中是否有环。如果有环则返回true，否则返回false。
数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
这个分析还有点难想到.我们这里设置一个快节点,每次走两步,fastNode = fastNode.next.next;慢节点每次走一步,slowNode = slowNode.next;假设有一个环形跑道,有两人在同一起跑线出发,一个人跑得快,一个人跑得慢,那么,这两个人肯定会相遇.所以,如果链表有环的话,fastNode 与 slowNode 一定会相遇,也就是
fastNode == slowNode;
这里需要注意的是,循环的条件中,由于fast走在slow的前面,所以,如果fastNode != null时.slowNode也不会为null.另外,除了要控制fast != null外,由于引用了fast.next的next,所以需要判断一下fast.next是否为空.
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
}
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围： 10000n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)
这个题的做法有点难想,这个是使用了数学问题加以解决的.
如下图所示,若有两个节点从head处出发,fast节点的速度是slow节点的2倍,二者在相遇处相遇,那么,通过解一个方程.
如图,快节点的路程为-------x + 环的总长度 + 环长度 - y
慢节点的路程为------------- x + 环长度 - y
快节点的路程 = 慢节点的路程 x 2
设环的总长度为n
x + n + n - y = 2 * (x + n - y)
x + 2n -y = 2x + 2n - 2y
x = y
所以,在fast,slow相遇后,令slow从head处出发,与fast以同一速度前进,相遇处就是环的入口处.
没啥好说得了,注意如果链表没有环,要返回null.
public ListNode EntryNodeOfLoop(ListNode pHead) {
//找环的入口处,也就是跑道的入口处,返回入口节点
//找环的入口点，起始点到入口点的距离与相遇点到入口距离相等，找到相遇点.
//让slow回到head,同fast一起走，相遇的点为环入口
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
slow = pHead;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}