题解 | #判断链表中是否有环#

package main

import . "nc_tools"

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

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
func hasCycle(head *ListNode) bool {
	// write code here
	// write code here
	// 环的定义，遍历过的节点，出现在某个节点的next。
	// 1. 需要记录遍历过的节点
	// 2. 能够确认next出现过
	// 假如某个节点的next和current的next一致。
	// 对链表进行翻转，最后，如果是有环的，最后的节点等于开始的节点，如果没有环那么会遍历结束。
	reverseHead := &ListNode{}
	reverseHead.Next = head
	prev := reverseHead
	cur := head

	// 遍历节点
	for cur != nil {
		temp := cur.Next
		cur.Next = prev
		prev = cur
		cur = temp
		if cur == reverseHead {
			return true
		}
	}

	return false
}