Golang leetcode142 环形链表 暴力map 快慢指针法

2024-01-07 17:29:00

环形链表 leetcode142

该题目要求找到入环的第一个节点
我们可以通过map进行记录,没到新的节点查询是否经过原有节点
入环节点,上两个节点的next相同
若有入环节点,则一定能检测到;若没有,则总会到达最后节点

暴力遍历 map哈希记录

// 暴力遍历 map哈希表记录
func detectCycle(head *ListNode) *ListNode {
	dummyHead := &ListNode{Next: head}
	table := map[*ListNode]int{}

	//若不成环,会走出循环
	for dummyHead.Next != nil {

		if _, ok := table[dummyHead.Next]; ok {
			return dummyHead.Next
		}
		table[dummyHead.Next] = 1
		dummyHead = dummyHead.Next
	}
	return nil
}

时间、空间复杂度都为O(n)

快慢指针法

思路解析

  1. 什么如果成环,快指针一定会再慢指针没有转完一圈之前追上满指针?

    1. 由于快指针的移动速度为2,慢指针的移动速度为1, 二者相对速度为1
      所以当快指针跟在慢指针后面时有以下几种情况

      • 快指针落后2 -> 快指针落后1 ->重合
      • 快指针落后1 ->** 重合**
      • 快指针与慢指针重合
        所以说只要快指针从后面追上慢指针,一定重合
    2. 最极端的情况:刚进入节点时,慢指针此时在相交节点上,快指针在慢指针前面一个
      在这里插入图片描述

      • 我们设到相遇所需的步数为x环长为n
      • 当相遇时,应该两个指针走过的节点数相同
      • 快指针由于是转了一圈再追上慢指针,其长度计算前去圈长
      • 快指针初始+1,LENfast=2x+1-n
      • 慢指针长度LENslow=x
      • 二者相同时,2x+1-n=x -> x=n-1
        也就是说即使在最极端的情况下也能在慢指针还没走完第一圈,到倒数第一个节点时与快指针相遇
  2. 得到二者一定相遇时,我们如何确定到底哪个节点是入环节点?
    在这里插入图片描述

    • 到相遇时,快指针走过的总距离F=a+n(b+c)+b ,n为快指针转过的圈数
    • 慢指针走过的距离S=a+b
    • 此时S=F,即a+n(b+c)+c=a+b -> a=(n-1)(b+c)+c
    • 通过这个方程我们可以看出来初始节点距离相交节点的距离为 n-1圈 圈长加c,而相遇节点距相交节点的距离为c
    • 所以从相遇节点和初始节点各出一个指针,总会在慢指针走完n-1圈在走玩c后在相交节点相遇
      在这里插入图片描述
// 双指针法 快慢指针
func detectCycle(head *ListNode) *ListNode {
fast, slow := head, head
//若有相交节点,则快慢指针一定会相遇
for fast != nil && slow != nil {
slow = slow.Next

//防止fast指针超出链表限制
if fast.Next == nil {
return nil
}

fast = fast.Next.Next

//从相遇节点开始寻找相交节点
if fast == slow {
//题目要求不修改链表
p := head
for p != slow {
slow = slow.Next
p = p.Next
}

return p

}
}
return nil
}


文章来源:https://blog.csdn.net/kingsill/article/details/135425304
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。