Leetcode 141.环形链表

Posted on |

114.环形链表

题目

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

1
2
3
4
5
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

方法

方法1：哈希表 & 字典

判断链表是否有环，只需要按段在当前结点之前的结点是否访问过。采用哈希表

逐个结点遍历，并且用哈希表记录每个节点的 reference (or memory address) 。如果当前节点是None，即遍历指针到达链表的尾部，说明该链表一定不是环形的。如果当前结点的reference在哈希表里，则一定是环形的。

  • 时间复杂度：O(N)，最多访问链表里的所有元素N。增加结点到字典里，仅花费时间O(1)
  • 空间复杂度：O(N)，空间进决定于加入到哈希表的元素数量，最多包含N个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        dic={}
        while head:
            if head in dic:
                return True
            dic[head]=0
            head=head.next
        return False

方法2：快慢指针

两个指针速度不一样：慢指针和快指针。慢指针每次移动一个结点，快指针每次移动两个结点。
如果链表中没有环形，快指针会最终到达终点None。
如果链表中有唤醒，假设快慢指针是在环形跑步的两个runner，快指针最终会遇上慢指针。假设快指针尽在慢指针后一步，那么下一次迭代，快指针走两步，慢指针走一步，这是快慢指针就遇上了。

  • 时间复杂度：O(n),n表示链表中的元素数量。

    • 如果无环，O(n)
    • 如果有环，将链表分为有环和无环部分。
    1. 在到达环之前，慢指针走了“non-cycic length”。此时，快指针已经到达环。$ 迭代次数=non-cycic length=N$
    2. 当快慢指针都在环内。快指针走两步，慢指针走一步，速度差是1，当快指针追上慢指针需要迭代次数是。距离最多是环的长度”cycle length K”，速度差是1.所以$迭代次数=almost ‘cycle length K’$

    因此，最差的时间复杂度是O(N+K),那就是O(n)

  • 空间复杂度：O(1)，只采用快慢指针，所以是O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False

        fast=slow=head
        while slow!=fast:
            if not fast or not fast.next:
                return False
            slow=slow.next
            fast=fast.next.next
        return True
```  


```Python
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast=slow=head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next

            if slow==fast:
                return True
        return False