23.md

链表中环的入口结点

题目

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000 节点值范围：[1,10000] 要求：空间复杂度 O(1)，时间复杂度 O(n)

示例

例如，输入{1,2},{3,4,5}时 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表 这个例子环的入口结点的结点值为3，所以返回结点值为3的结点

思路

• 快慢指针，和判断链表中是否有环是一回事儿
• 简单说就是如果有环，两个人速度不一样跑着跑着是一定会套圈的
• 相遇点不等于是环的入口，画图比划
• 【头结点到入口距离等于相遇点到入口的距离】
• 那么在相遇时，将快指针fast重新放到头结点A
• 慢指针slow的位置不变，且快指针的速度改为与慢指针slow相同
• 那么快指针fast从头结点A走过X路程后到达环的入口结点
• 慢指针slow从快慢指针相遇节点走过x路程后也到达了环的入口结点
• 也即他们再次相遇时的节点就是环的入口结点

实现

package main

import (
	"fmt"
	"time"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

// 链表中环的入口结点
func main() {
	var entry = &ListNode{
		Val:  3,
		Next: nil,
	}
	var circle *ListNode
	for k, v := range [2]int{5, 4} {
		var node ListNode
		if k == 0 {
			node = ListNode{
				Val:  v,
				Next: entry,
			}
		} else {
			node = ListNode{
				Val:  v,
				Next: circle,
			}
		}
		circle = &node
	}
	entry.Next = circle
	var start *ListNode
	for k, v := range [2]int{2, 1} {
		var node ListNode
		if k == 0 {
			node = ListNode{
				Val:  v,
				Next: entry,
			}
		} else {
			node = ListNode{
				Val:  v,
				Next: start,
			}
		}
		start = &node
	}
	// ReviewAll(start)
	EntryNodeOfLoop(start)
}

func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	var fast *ListNode = pHead
	var slow *ListNode = pHead
	for {
		if fast == nil || fast.Next == nil {
			break
		}
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			break
		}
	}
	if fast == nil || fast.Next == nil {
		var empty *ListNode
		return empty
	}
	fast = pHead
	for {
		if fast == slow {
			break
		}
		fast = fast.Next
		slow = slow.Next
	}
	return fast
}

func ReviewAll(pHead *ListNode) {
	for {
		if pHead == nil {
			break
		}
		fmt.Println(pHead.Val)
		time.Sleep(time.Duration(1) * time.Second)
		pHead = pHead.Next
	}
}