算法面试题05 - 链表中是否有环

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos是 -1，则在该链表中没有环。
注意：pos不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。否则，返回false。

要求:
使用快慢指针的方法判断给定链表是否有环，时间复杂度应为 O(N)，空间复杂度应为 O(1)。
代码实现需要定义快慢指针，快指针一次走两步，慢指针一次走一步,如果快慢指针相遇则说明有环，实现这一算法。

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

答案：

public class ListNode {
    public var data: Int
    public var next: ListNode?
    public init(_ data: Int) {
        self.data = data
        self.next = nil
    }
}

func hasCycle(_ head: ListNode?) -> Bool {
    
    var slow: ListNode? = head
    var fast: ListNode? = head
    
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        
        if slow === fast {
            return true
        }
    }
    
    return false
}

let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 //创建环，pos=1

let head = node1

print(hasCycle(head)) //true

知识点详解：

链表：链表是一种常见和重要的数据结构，主要有一下几点需要理解：

1. 链表由一系列节点(Node)组成，每个节点包含数据域data和指针域next。
2. 数据域用于存储节点的数据，指针域用于指向下一个节点。
3. 链表中的节点使用指针连成一串，每个节点指针都指向下一个节点，这样就构成了链表。
4. 链表有一个头节点head，作为链表的入口，头节点不存储数据。(链表也可以没有头节点)
   (单)链表.png

pos：表示链表尾部连接到链表中的位置(索引从0开始)。也就是说，如果链表中有环，pos就表示环的入口节点的索引。例如：pos默认-1，表示没有环，如果再第一个节点上有环那么pos就是0，pos=1那么第二个节点就是环的入口，pos=2环的入口在第三个节点上，以此类推...pos不会作为输入参数传入函数，仅仅表示了链表是否有环以及环的入口在链表中的位置。实际上，我们不需要知道pos的具体值，只需要通过快慢指针判断链表是否存在环即可。

===：三个等号操作符表示指针比较，判断两个指针是否指向同一个节点。

算法思路

1. 定义快慢两个指针fast和slow，初始化都指向头节点head。
2. 每次快指针fast向前移动两步，慢指针slow向前移动一步。
3. 检查快慢指针是否相遇，如果fast === slow，则说明链表有环。
4. 如果快指针遇到null，说明链表无环。

时间复杂度分析：

转圈分析.png

0.快指针走的速度是慢指针的两倍
1.在环外的时候慢指针在后，快指针在前，不可能重合
2.在环内，快指针走几步追上了慢指针。
3.快指针到末尾还没相遇，说明无环。
结论：时间复杂度O(N)。

空间复杂度

该算法仅使用了两个额外的指针：快指针fast和慢指针slow，空间消耗都是常数级的，不随链表长度N增加而改变。空间复杂度是O(1)。

BTW

这道题的题目分析、要求和示例与题目无关，🤔
感谢各位简友的宝贵时间与意见！文章难免有疏漏或错误，如有涉及不当之处，还望能够提出宝贵意见。感激不尽！