leetcode-141 环形链表

留言

141. 环形链表

难度: 简单


(经典的)快慢指针法:


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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {

    if head == nil {
        return false
    }

    slow := head
    fast := head

    for fast != nil && fast.Next != nil { //之所以还要加fast != nil的判断(且必须在前),是为了短路,防止报错,见后面的代码
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }

    }
    return false
}

为何还要加fast != nil的判断且必须在前面?


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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package main

import "github.com/davecgh/go-spew/spew"

func main() {

	l0 := &ListNode{}

	l0.Val = 100

	l1 := &ListNode{}

	l1.Val = 207

	l0.Next = l1

	spew.Println(l0)

	spew.Println("--------------")

	hasCycle(l0)

}

// * Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {

	if head == nil {
		return false
	}

	slow := head
	fast := head

	for fast.Next != nil {

		spew.Println("此时慢指针的下一个节点是:", slow.Next)
		spew.Println("此时快指针的下一个节点是:", fast.Next)
		slow = slow.Next
		fast = fast.Next.Next

		spew.Println("此时慢指针的下一个节点是:", slow.Next)
		spew.Println("此时快指针的下一个节点是:", fast.Next)

		//cs := fast.Next.Next.Next.Next.Next.Next //在不打印,不判别时,不会报错,可以一直写下去
		//spew.Println(cs)

		if slow == fast {
			return true
		}
	}

	return false

}

输出为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<*>{100 <*>{207 <nil>}}
--------------
此时慢指针的下一个节点是: <*>{207 <nil>}
此时快指针的下一个节点是: <*>{207 <nil>}
此时慢指针的下一个节点是: <nil>
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x8 pc=0x10be51e]

goroutine 1 [running]:
main.hasCycle(0xc0000102d0, 0x1)
	/Users/shuangcui/go/src/leetcode/141.go:49 +0x1ae
main.main()
	/Users/shuangcui/go/src/leetcode/141.go:21 +0xfb
exit status 2

如上代码中,传入一个有两个元素的链表.

因为 快指针fast 不是顺次遍历,而是跳跃,如果不加fast != nil的条件,且不放在判别式的前面, 就会出现如上报错,即在判定(或打印)下下个指针时,会出现越界而报错.

第一次遍历后,各变量指针的指向:

如果不加fast != nil的条件,且不放在判别式的前面,那fast.Next越界而发生panic