判断链表中是否有环

发表于

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围： 链表长度 0≤n≤10000 ，链表中任意节点的值满足 |val|≤100000

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例1

1
2
3
输入:  {3,2,0,-4},1
返回:  true
说明:  第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true

示例2

1
2
3
输入:  {1},-1
返回:  false
说明:  第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

示例3

1
2
输入:  {-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回:  true

题解

快慢指针

我们使用两个指针，fast 与 slow。

它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

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
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
*/
func hasCycle( head *ListNode ) bool {
    // write code here
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}