快慢针判断链表成环

快慢针常用来判断链表是否成环，成环则返回第一个环起点。通常快指针两个步长，慢指针一个步长。

简图如下

        ⬇️<-<-<-⬆️
        ⬇️      ⬆️
♦️－>->->⬇️->->->⬆️
A       B       C

思路

判断是否相遇只要看快慢针会不会相遇就行了
//一般情况都是快针2个步长，慢针1个步长
假设会在C处相遇，这个时候慢针走了N步(不一定就是A -> B -> C，可能慢针也转了几圈，这个不影响推导，别被绕进去了), 快针就走了2N步。也就是说从C处开始，慢针再走N步就可以再一次到C处了(不用去想中间转了几圈，不然又被绕进去了)，既然都可以到C，那么就一定能在入口处B相遇了。so我们可以把快针(慢针也无所谓啦，都指向同一个结点了)退回到A点，和慢针一样一个步长，再次相遇点就是入口处B点了。

思路清晰了，-接下来就是算法实现了

(head) => {
	let slow = head;
	let fast = head;
	while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            slow = head;
            while(slow!=fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }
}

可以利用快慢针巧妙地判断两条单链表是否成环。

//
function solution(headA, headB) {
    if(!(headA || headB)) return null;
    //让B链表成环，如果A和B链表相交的话，B链表成环则A链表就一定也成环，且环入口即为两条链表相交的点。
    let last = headB;
    while(last.next) {
        last = last.next;
    }
    last.next = headB;
    
    let slow = headA;
    let fast = headA;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            fast = headA;
            while(slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            last.next = null;
            return fast;
        }
    }
    last.next = null;
    return null;
}

说一下，这个算法的执行用时是60ms(emmm…)，有个问题待讨论，把变量声明let换成var用时是64ms.