数组与链表实战 （算法与数据结构系列 4）

说的不如练的，今天进行数组和链表实战训练，实战篇我会给出我的解题思路，以及如何运用我之前文章说过的方法一步一步去解决问题。

判断链表是否有环

https://leetcode.com/problems/linked-list-cycle/

• 第一步，看清楚题目，理解题意，全面分析要考察的点。
  判断是否有环只是明面，还有解题思路是否全面，是否考虑到空链表，单节点链表等。

• 第二步，分析可能的解法，选出最优解并解题
  这里给出两个我想到的思路
  1）遍历链表，将出现过的节点存在 map 中，每遍历一个节点，从 map 中查找是否出现过，如果出现过代表存在环。
  2）假设有两人在环形操场跑步，A 速度快，B 速度慢，那么迟早有个时刻 A 会超过 B 一圈。此题同理，指定两个遍历器 T1 和 T2 同时出发，T1每次遍历一个节点，T2 每次遍历两个节点，若 T1 T2 相遇，则链表必定有环。

因为题目给出要求：Can you solve it using O(1) (i.e. constant) memory? 故采用解法 2

这里给出此算法 2 成立的数学证明：

前提定理：a ≡ b(mod m) 则 m | (a - b)，反之亦然。
a，b 同余则 m 整除 a - b，m 整除 a - b则a，b 同余。
22 % 4 = 2
90 % 4 = 2
则 4 整除 68

先假设链表有环，两个遍历器相遇了，则有：
设 K 为慢迭代器走的路程，2K 为快迭代器走的路程，T 为进入环之前的路程，L 为环长。
则 (2K - T) mod L = (K -T) mod L
则 L | (2K - T) - (K -T) = L | K，因为 L 为无穷大时，则 K 为无穷大，而 L 存在且确定时，K 也有解。也就是说无环，则不可能相遇，有环则必定相遇。

这里需要大家仔细看，并结合画图理解，但是这应该是比较好理解的证明方式了。

下面给出实现代码（其实有了思路之后是比较简单的，关键是思路），注意特殊链表的处理：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    bHas := false
    
    if head == nil {
        return bHas
    }

    s1, s2 := head, head
    for {
        if s2.Next != nil && s2.Next.Next != nil {
            s1 = s1.Next
            s2 = s2.Next.Next
            
            if s1 == s2 {                     //相遇
                bHas = true
                break
            }
            continue
        } else {
            break                             //到达尾节点，无环
        }
    }
    
    return bHas
}

还没结束呢

• 第三步，提交代码查看算法效率，并且进入讨论区看看别人的解题思路，如果可能，对自己的算法进行优化。
  image.png

系列会持续更新，需要查看可以进我主页。
如有疑问或者发现错误和纰漏，请留言指正。