go语言每日一练——链表篇(六)

传送门

牛客面试必刷101题—— 判断链表中是否有环
牛客面试必刷101题—— 链表中环的入口结点

题目及解析

题目一

代码

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}

	slow := head
	fast := head.Next

	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		fast = fast.Next.Next
		slow = slow.Next
	}

	return true
}

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

题目二

代码

package main

func EntryNodeOfLoop(head *ListNode) *ListNode {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			fast = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow
		}
	}
	return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

今天的解题算法主要使用了双指针这一算法，我们利用定义快慢指针来判断链表中是否有环以及环的节点，这里的理论依据主要是floyd判圈算法，大家有兴趣的化可以看一下文末的文章来理解一下该算法，这里就不做赘述了

拓展

floyd判圈算法