判断单链表是否有环及两个链表是否相交

判断单链表是否有环 思路：设置两个指针，都从头结点开始向前遍历，一个速度快，一个速度慢，若链表存在环，那么两个指针一定会相遇的 代码实现：

const hasCycleOfList = function(head) {
    if(!head) return null
    let slow = fast = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if(slow === fast) {
            return slow //如果相遇，return相遇的结点，即环的入口
        }
    }
    if(!fast || !fast.next.next) return null
}

注意若有环，一个走1步，一个走2步，这种方式fast一定会与slow相遇而不会跳过slow，因为开始两者之间的距离一次增加1步，1, 2, 3, 4, …，当两者都进入环后，差距则是一步一步的缩小，4，3，2，1，0，到0的时候就重合了。若fast是每次走3步，则就不一定能重合了。

判断两个链表是否相交 思路：

传统方法：两层循环

hash：遍历第一个链表，将第一个链表中的每个节点的地址存入hash表中，再遍历第二个链表，计算hash值，如果当前结点的地址和hash值都已存在hash表中，那么就判断这两个链表相交

const isEncounter = function(listA, listB) {
 if(!listA || !listB) return null
 let p= listA, q= listB, map = {}
 while(p) {
     map[p] = 1
     p= p.next
 }
 while(q) {
     if(map[q]) {
         return true
     }
     q= q.next
 }
 return false
}

其中一个首尾相接：将第一个链表的尾结点的next指向该链表的头结点，然后再遍历第二个链表，如果在遍历的过程中能达到第一个链表的头部，那么就判断这两个链表相交

const isEncounter = function(listA, listB) {
 if(!listA || !listB) return null
 let p = headA = listA, q = listB
 while(p.next) {
     p = p.next
 }
 p.next = headA
 while(q) {
     if(q === headA) {
         return true
     }
     q = q.next
 }
 return false
}

根据尾结点判断：如果两个链表相交的话，那么这两个链表从他们相交的那个结点往后都是一样的，那么就是说，它们的尾结点肯定也是一样的

const isEncounter = function(listA, listB) {
 if(!listA || !listB) return null
 let p= listA, q= listB
 while(p.next) {
     p= p.next
 }
 while(q.next) {
     q= q.next
 }
 return p === q
}

计算相差的长度：首先分别计算两个链表的长度（长度已知就不需要），然后让长度长的链表先前进（lengthMax - lengthMin）步，最后同时遍历这两个链表，遇到相等的情况就判定这两个链表相交

const isEncounter = function (listA, listB) {
 if (!listA || !listB) return false
 let p = listA, q = listB, lenA = lenB = 0
 while (p) { lenA++; p = p.next }
 while (q) { lenB++; q = q.next }
 if (lenA > lenB) {
     while (lenA - lenB) {
         p = p.next
         lenB++
     }
 } else {
     while (lenB - lenA) {
         q = q.next
         lenA++
     }
 }
 while (p && q) {
     if (p === q) {
         return true
     }
     p = p.next
     q = q.next
 }
 return false
}

判断单链表是否有环及两个链表是否相交

CATALOG