【leetcode系列】给定一个单链表，判断单链表中是否有环

太过爱你忘了你带给我的痛 2022-12-08 15:35 132阅读 0赞

## 给定一个单链表，判断链表中是否有环。 ##

### 题目背景 ###

> [141. 环形链表][141.]——给定一个链表，判断链表中是否有环。
> 
> 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。
> 
> 如果链表中存在环，则返回 `true` 。 否则，返回 `false` 。
> 
> **进阶：**
> 
> 你能用 *O(1)*（即，常量）内存解决此问题吗？
> 
> **示例 1：**
> 
> ![4a18acda10c1606aa5d1132b9de26d61.png][]
> 
>     输入：head = [3,2,0,-4], pos = 1
>     输出：true
>     解释：链表中有一个环，其尾部连接到第二个节点。
> 
> **示例 2：**
> 
> ![1a6fcfc68d7340c39151075f7fa53150.png][]
> 
>     输入：head = [1,2], pos = 0
>     输出：true
>     解释：链表中有一个环，其尾部连接到第一个节点。
> 
> **示例 3：**
> 
> ![3039274e08a9385ea77b20a81060ed40.png][]
> 
>     输入：head = [1], pos = -1
>     输出：false
>     解释：链表中没有环。
> 
> **提示：**
> 
>  *  链表中节点的数目范围是 `[0, 104]`
>  *  `-105 <= Node.val <= 105`
>  *  `pos` 为 `-1` 或者链表中的一个 **有效索引** 。

### 思路1代码： ###

> 判断一个单链表是否有环,  
> 可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.  
> 其实 可以遍历这个单链表, 访问过后,  
> 如果这个节点 不在 set 里面, 把这个节点放入到 set 集合里面.  
> 如果这个节点在 set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环  
> 如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

class Solution1:
        """
        思路分析:
        判断一个单链表是否有环,
        可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
        其实 可以遍历这个单链表, 访问过后,
        如果这个节点 不在 set  里面, 把这个节点放入到 set 集合里面.
        如果这个节点在  set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环.
        如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.
    
        """
    
        def hasCycle(self, head):
            mapping = set()
            flag = False
            p = head
            while p:
                if p not in mapping:
                    mapping.add(p)
                else:
                    flag = True
                    break
                p = p.next
    
            return flag

###  思路2代码： ###

> 定义 两个指针, 一个快指针fast, 一个慢指针slow, 快指针一次走两步,慢指针一次走一步.  
> 如果 两个指针相遇了, 则说明链表是有环的.  
> 如果 fast 都走到null了, 还没有相遇则说明没有环.

class Solution2:
        """
        定义 两个指针, 一个快指针fast, 一个慢指针slow,  快指针一次都两步,慢指针一次走一步.
        如果 两个指针相遇了, 则说明链表是有环的.
        如果 fast 都走到null了, 还没有相遇则说明没有环.
        """
    
        def hasCycle(self, head):
    
            flag = False
            if head is None or head.next is None or head.next.next is None:
                return flag
    
            fast = head.next.next
            slow = head.next
    
            while fast is not slow:
    
                if fast.next is None or fast.next.next is None:
                    # no circle
                    return flag
                fast = fast.next.next
                slow = slow.next
    
            # 相遇肯定有环
            if fast is slow:
                # hasCircle
                flag = True
    
            return flag

### 样例测试： ###

class Node:
        def __init__(self, data, next):
            self.data = data
            self.next = next
    
    
    if __name__ == '__main__':
        print "测试样例1"
        n1 = Node('n1', None)
        n2 = Node('n2', n1)
        n3 = Node('n3', n2)
        n4 = Node('n4', n3)
        n5 = Node('n5', n4)
        obj1=Solution1()
        print obj1.hasCycle(n5)  # False
        obj2 = Solution2()
        print obj2.hasCycle(n5)  # False
    
        print "测试样例2"
        ln1 = Node('n1', None)
        ln2 = Node('n1', None)
        ln3 = Node('n1', None)
        ln4 = Node('n1', None)
        ln5 = Node('n1', None)
        ln5.next = ln4
        ln4.next = ln3
        ln3.next = ln2
        ln2.next = ln1
        ln1.next = ln3
        obj1 = Solution1()
        print obj1.hasCycle(ln5)  # True
        obj2 = Solution2()
        print obj2.hasCycle(ln5)  # True

参考：[https://blog.csdn.net/u010339879/article/details/86664813][https_blog.csdn.net_u010339879_article_details_86664813]

[141.]: https://leetcode-cn.com/problems/linked-list-cycle/
[4a18acda10c1606aa5d1132b9de26d61.png]: /images/20221123/5fa2584df9c44be6a8e70fe4ba94aaa2.png
[1a6fcfc68d7340c39151075f7fa53150.png]: /images/20221123/770ee0d8a4f24b2a8eded1d40e1cfe5f.png
[3039274e08a9385ea77b20a81060ed40.png]: /images/20221123/0ae1196085cd4e4c9c6e3b14152c898a.png
[https_blog.csdn.net_u010339879_article_details_86664813]: https://blog.csdn.net/u010339879/article/details/86664813