leetcode算法题之142 - 环形链表 II

最近公司经济不景气导致团队被迫处在了解散边缘，而后周末之余在力扣上刷题时发现有些题目的解题思路挺有趣的，就比如这个 142 - 环形链表 II ，题目难度是中等，它是 141 - 环形链表的升级版，首先附上我自己的解题思路，也是官方题解的方法一：哈希表

首先通过事先声明一个 map ，下标为链表结构，每次遍历时将遍历的链表结构存入该 map 中，然后如果下次遍历时 map 中已存在相同链表结构的数据，直接返回即可。以下是代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    nodeMap := make(map[*ListNode]struct{})
    for head != nil {
        if _, ok := nodeMap[head]; ok {
            return head
        }

        nodeMap[head] = struct{}{}
        head = head.Next
    }

    return nil
}

141 - 环形链表这题的解题方式我也是这样的，只不过就是将第一次 return 的 head 换成 true，第二次 return 的 nil 换成 false。

这种方式因为需要经历一层 for 循环，所以时间复杂度为 O(N) ，又因为需要 map 动态存储已遍历过的链表结构，所以空间复杂度也为 O(N) ，所以该题还存在更优的解题方式。

后面通过官方题解的文章知道了还存在一种叫「Floyd 判圈算法」（又称龟兔赛跑算法）的思路，通俗理解就是设置一个快指针比一个慢指针更快一步，然后他们在迭代N圈后一定会相遇（我的理解是快指针在通过环形迭代一圈后），这里就可解决 141 - 环形链表这道题的解题答案。

附上解题代码：

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

    // 快慢指针
    slow := head
    // 快指针要比慢指针先一步，否则for循环无法进入
    fast := head.Next

    for slow != fast {
        if fast == nil || fast.Next == nil { // 无环
            return false
        }

        // 慢指针每次走一步
        slow = slow.Next
        // 快指针每次走两步
        fast = fast.Next.Next
    }

    // 相遇即是有环
    return true
}

而 142 - 环形链表 II 这道题的解题思路也可使用龟兔赛跑算法来解，但是需要先找到它的规律，也就是解题公式（看公式我怎么也不懂，其实就是数学太烂了🤦‍♂️）。

其实上面这段代码逻辑中，到有环的这一步，快指针的移动路径已经是慢指针的两倍了，到这个点上你会发现如果两个指针一个从起点开始一个从这个位置开始，每次前进一步，而他们最终会在环形入口处相遇。

用代码呈现就是：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    // 快慢指针
    slow := head
    fast := head.Next

    for slow != fast {
        if fast == nil || fast.Next == nil { // 无环
            return nil
        }

        slow = slow.Next
        fast = fast.Next.Next
    }

    // 有环
    // 找到环的入口
    // 其实到这之后，再将slow置于初始位置，同fast一步一步前进便会相遇，而且是在入口相遇
    slow = head
    fast = fast.Next
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }

    // 相遇即是入口
    return slow
}

这种方式也是因为需要经历一层 for 循环，所以时间复杂度为 O(N) ，但因为只使用了两个指针就解决了入口取值问题，所以空间复杂度是 O(1) ，为最优解法。

参考文献：
环形链表 - leetcode官方题解
 环形链表 II（双指针法，清晰图解）

leetcode算法题之142 - 环形链表 II

发表评论