题目
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
解法
set数据结构
set数据结构每个遍历的节点都留痕,如果碰到重复的就说明从这里就开始入环了
// JavaScript
var detectCycle = function(head) {
if(head == null || head.next == null) return null
let curr = head
let arr = []
while (curr.next) {
if (arr.includes(curr)) {
return curr
} else {
arr.push(curr)
curr = curr.next
}
}
return null
};
龟兔赛跑
设定一个快指针和慢指针,快指针比慢指针移动的快一步,如果有环,肯定会相遇,相遇的时候记录一下相遇的节点,然后再新建一个指针从头开始移动,相遇的指针也一起移动,两个指针肯定会相遇,相遇的那个节点,就是开始入环的节点。
// JavaScript
var detectCycle = function(head) {
if(head == null || head.next == null) return null
let fast, slow, meet
fast = slow = head
let hasCycle = false
while (fast && slow && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
hasCycle = true
meet = slow
break
}
}
if(hasCycle) {
let curr = head
while(curr != meet) {
curr = curr.next
meet = meet.next
}
return curr
}
return null
};
解法分析
第一种相对来说比较直观,时间复杂度是O(n)的,但是空间复杂度较高,需要借助新的变量空间来记录遍历过的节点。
第二种方法时间复杂度也是O(n),但是空间复杂度较第一种会低很多,算是比较经典的解法。
github代码地址