【LeetCode】141. 环形链表

[WGrape]

介绍

https://leetcode-cn.com/problems/linked-list-cycle/

思路

1、哈希表，遍历整个链表，每遇到一个节点就存下来，如果发现已存在，则表示有环
2、双指针（快慢指针），初始状态下，快慢指针都指向头节点，其中慢指针每次运动一个位置，快指针每次运动两个位置，如果两个指针指向一致重合，则说明有环。

无论使用哪种思路，判断链表中节点关系（是否是同一个节点）时，需要通过判断地址是否一样

解题

双指针

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

 // 移动快指针
func moveFastPointer(p *ListNode) *ListNode {
	if p.Next == nil {
		return nil
	}
	return p.Next.Next
}

// 移动慢指针
func moveSlowPointer(p *ListNode) *ListNode {
	return p.Next
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
		return false
	}

	slow := head
	fast := head
	first := true
	for {
		// 初始状态开始
		if first {
			fast = moveFastPointer(fast)
			slow = moveSlowPointer(slow)
			first = false
			continue
		}

		// 快指针已移动到链表末尾, 慢指针还在链表中
		// 链表遍历提前结束
		if fast == nil {
			break
		}

		// 快指针追上慢指针
		if slow == fast {
			return true
		}

		// 快慢指针移动
		fast = moveFastPointer(fast)
		slow = moveSlowPointer(slow)
	}

	return false
}