快慢指针判断链表是否有环及环起点
判断是否有环
方法
- fast和slow都指向head，然后fast每次走2步、slow每次走1步。
- 如果fast和slow相遇（fast=slow）即为有环。
- 如果fast或fast.next为尾节点next，即为无环
原理
- fast和slow都指向head，然后fast每次走2步、slow每次走1步。
- 如果有环，fast先进入环。然后等slow进入环后，每次移动，fast和slow之前的距离-1，fast和slow必定相遇。
- 如果无环，则fast或者fast.next会指向链表尾节点的next，即null
function judege(head) {
if (head === null) return false;
let slow = head;
let fast = head;
while(fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast) return true;
}
return false;
}
找环的起点
方法
- 快慢指针相遇后，慢指针指向头节点，然后快慢指针每次都移动1步，当快慢指针相遇时（fast=slow),快慢指针都指向了环入口节点
原理
- 假设链表头节点距离环入口a。快慢指针相遇时，相遇点距离环入口b,快指针绕了环n圈。环的长度L。
- 那么相遇时慢指针走了a+b，快指针走了a+nL+b。快指针步数是满指针的2倍，得出 2(a+b)=a+nL+b, 简化得到a+b = nL。
- 相遇时，慢指针回到头节点，快慢指针每次移动1步。慢指针走到环入口时，走了a步，快指针也走了a步。此时快指针的位置为a+b，上一步知道a+b=nL,快指针此时也在环入口位置，此时快慢指针相遇。
function getCircleNode(head) {
if (head === null) return null;
let slow = head;
let fast = head;
while(fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if(fast === slow) break;
}
if (fast === null || fast.next === null) return null;
slow = head;
while(fast !== slow) {
slow = slow.next;
fast = fast.next;
}
}
