leetcode刷题笔记一百四十一题与一百四十二题 环形链表与环形链表2
源地址：
问题描述：
141题问题描述
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。142题问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
//141题 142题 思路基本一致，不同在于141返回是否有环 142返回环入口
//大体思路可以分为两种，一种是哈希，另一种是基于数学原理的快慢指针
//哈希表法
//141
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
import scala.collection.mutable
object Solution {
def hasCycle(head: ListNode): Boolean = {
var start = head
val HSet = mutable.Set[ListNode]()
while (start != null){
if (HSet.contains(start)) return true
else HSet.add(start)
start = start.next
}
return false
}
}
//142
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
import scala.collection.mutable
object Solution {
def detectCycle(head: ListNode): ListNode = {
var start = head
val HSet = mutable.Set[ListNode]()
while (start != null){
if (HSet.contains(start)) return start
else HSet.add(start)
start = start.next
}
return null
}
}
//数学原理快慢指针基于题解：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
//即快慢指针进行两次相遇，第一次相遇判断有环，第二次相遇判断环入口
//2 * dis(slow) = dis(fast)
//2 * (F[链表头到环入口] + a[环入口到一次相遇点]) = F + a + a + b[剩余环内部分] + （完整环 忽略）、
// F = b
//一次相遇后，slow fast指针同步移动，二次相遇点即为环入口
//141
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def hasCycle(head: ListNode): Boolean = {
if (head == null || head.next == null) return false
var slow = head
var fast = head.next
while (slow != fast){
if (fast == null || fast.next == null) return false
slow = slow.next
fast = fast.next.next
}
return true
}
}
//142
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def detectCycle(head: ListNode): ListNode = {
var slow = head
var fast = head
while (true) {
if (fast == null || fast.next == null) return null
fast = fast.next.next
slow = slow.next
if (fast == slow) {
slow = head
while (fast != slow) {
fast = fast.next
slow = slow.next
}
return fast
}
}
return null
}
}