Golang Leetcode 142. Linked List Cycle II.go

anakinsun

发布于 2019-05-10 18:28:31

5980

发布于 2019-05-10 18:28:31

文章被收录于专栏：学习日记学习日记

https://cloud.tencent.com/developer/article/1423917

思路

用快慢指针的方式，快指针每次走两步，慢指针每次走一步，相遇的时候，就是环的位置

此时slow停的位置到环入口的距离，等于头结点到环入口的距离（https://blog.csdn.net/jhlovetll/article/details/85255708）

所以两个结点前进相同的步数，head就位于环的入口处了

code

func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	slow, fast := head.Next, head.Next.Next
	for fast != nil && fast.Next != nil && slow != fast {
		slow, fast = slow.Next, fast.Next.Next
	}
	//没有环
	if slow != fast {
		return nil
	}
	for slow != head {
		slow, head = slow.Next, head.Next
	}
	return slow
}

更多内容请移步我的repo：https://github.com/anakin/golang-leetcode

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年04月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

https