初级算法-链表-环形链表

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

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

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

环形链表示例.png

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

条件分析:

1.环形链表判断 -> 链表操作,有环即可结束

解决思路1:

1. 根据分析1,采用哈希表来存储

定义可变链表,然后进行循环链表next,当next为空时跳出循环,然后判断哈希表是否存在该节点,如果存在则返回,如果不存在则将该节点加入哈希表.然后指向下一个next.如果都不存在,则返回不存在

func hasCycle(_ head: ListNode?) -> Bool {
    var node = head
    var set  = Set<ListNode>()
    while node?.next != nil{
        if set.contains(node!) {
            return true
        }
        set.insert(node!)
        node = node?.next
    }
    
    return false
}

环形链表 哈希表 提交结果.jpg

解决思路2:(原理可以理解为双人跑道跑步,然后快指针总能追上慢指针.如果一直没追上,说明一直在往前,没有环.如果存在环,则必定能追上.)

1. 根据分析1,可以采用快慢指针来进行判断

如果node为空则直接返回.定义快慢指针,然后循环判断,快指针,快指针的next,快指针的next的next.如果不为空,则快指针为自身的下三个节点.慢指针为慢指针的下一个节点.如果快指针等于慢指针,则存在,否则则不存在.

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

环形链表 快慢指针 提交结果.jpg

测试用例:

// 一个节点
let headNode = ListNode.init(1)

// 不是环形链表
let headNode = ListNode.init(1)
let firstNode = ListNode.init(2)
let secondNode = ListNode.init(3)
let threeNode = ListNode.init(4)
headNode.next = firstNode
firstNode.next = secondNode
secondNode.next = threeNode

// 是环形链表
let headNode = ListNode.init(1)
let firstNode = ListNode.init(2)
let secondNode = ListNode.init(3)
let threeNode = ListNode.init(4)
headNode.next = firstNode
firstNode.next = secondNode
secondNode.next = threeNode
threeNode.next = firstNode

考察要点:

• 哈希表
• 链表
• 双指针