【日拱一卒】链表——判断链表是否有环

需求

判定一个链表是否有环

0704-1-不存在环.png

这张图不存在环，头结点是1，尾结点是5。

0704-2-存在环.png

这张图中，节点2-3-4-5-2就构成了环。

思路

思路1 ——快慢指针

顾名思义，一个快指针，一个慢指针。

如果不包括环，快慢指针同向行驶，根据小学经典数学题，他们永远无法相遇，而且差距只会越来越大。

如果链表有环，意味着快慢指针都会调头，好比操场跑步，第一圈快指针在慢指针前面，但是后面快指针迟早会追上慢指针。所以可以借助这个思想，使用快慢指针判定是否有环。

0704-3-快慢指针.png

图中，slow代表慢指针，每次只走一步，fast代表快指针，每次走两步。

第一次：slow停在节点2，fast停在节点3

第二次：slow停在节点3，fast停在节点5

第三次：slow停在节点4，fast停在节点3

第四次：slow停在节点5，fas停在节点5

至此，快指针已经”撵上“了慢指针。

代码实现

func hasCycle(head *ListNode) bool {
    slow := head
    fast := head

    for fast.Next != nil && fast != nil {
        if slow.Val == fast.Val {
            return true
        } else {
            slow = slow.Next
            fast = fast.Next.Next
        }
    }

    return false
}

思路2——另辟蹊径

遍历链表，如果节点的值与一个特殊的值不相等，则将遍历过的节点的值设置成一个特殊的值，相当于打标记。

如果链表遍历完，发现所有节点都不等于这个特殊的值，则判定链表无环。

如果在遍历的过程中，发现有节点等于这个特殊的值，则认为有环。

代码实现

func hasCycle2(head *ListNode02) bool {
    if head == nil {
        return false
    }

    for head != nil {
        if head.Val == 5201314 {
            return true
        }

        head.Val = 5201314
        head = head.Next
    }

    return false
}

只能说，第一个想到这个思路的，脑洞是有多大~

不忘初心

老王：你不好好种地，你以后长大能干什么

小王：学算法

老王：学算法？！你数组、链表、栈、队列、堆、排序、查找都整不明白，你学什么算法

小王：我只学如何判断链表是否有环

老王：。。。