148 - 142 环形链表2

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

img

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。

img

进阶： 你是否可以不用额外空间解决此题？

解答

不许修改链表。。不然直接覆盖掉走过的路就行了。

感觉可以用快慢指针，然后看他们能不能追到

set

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        node = head
        while node != None:
            if node in visited:
                return node
            else:
                visited.add(node)
                node = node.next
        return None

Runtime: 44 ms, faster than 98.02% of Python3 online submissions for Linked List Cycle II.

Memory Usage: 16.3 MB, less than 100.00% of Python3 online submissions for Linked List Cycle II.

var detectCycle = function(head) {
  let visited = new Set()
  let node = head
  while (node !== null) {
    if (visited.has(node)) {
      return node
    }
    visited.add(node)
    node = node.next
  }
  return null
};

Runtime: 68 ms, faster than 68.47% of JavaScript online submissions for Linked List Cycle II.

Memory Usage: 37.8 MB, less than 18.75% of JavaScript online submissions for Linked List Cycle II.

func detectCycle(head *ListNode) *ListNode {
    visited := make(map[*ListNode]bool)
    node := head
    for node != nil {
        if _, ok := visited[node]; ok {
            return node
        }
        visited[node] = true
        node = node.Next
    }
    return nil
}

Runtime: 12 ms, faster than 11.07% of Go online submissions for Linked List Cycle II.

Memory Usage: 5 MB, less than 16.67% of Go online submissions for Linked List Cycle II.

快慢指针

感觉是一道数学题。。

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/shuang-zhi-zhen-qing-xi-ti-jie-zhen-zheng-cong-shu/

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/chun-lie-gong-shi-bi-mian-da-duan-wen-zi-jie-shi-s/

1. 快慢指针，相遇说明有环，不相遇返回null

2. 相遇后，一个指针留在相遇点继续向前，另一个指针直接回到起点，重新走，都是一步步走。

   他们的相遇点就是入环点

原因列公式解公式就能算出来了：非环部分的长度+环起点到相遇点之间的长度就是环的整数倍

也就是，起点到入环点距离，和相遇点到入环点的距离，是相等的

还是用set容易

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return
        fast = head
        slow = head
        while True:
            if not fast or not fast.next:
                return
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

Runtime: 48 ms, faster than 94.85% of Python3 online submissions for Linked List Cycle II.

Memory Usage: 16 MB, less than 100.00% of Python3 online submissions for Linked List Cycle II.

var detectCycle = function(head) {
  let fast = head
  slow = head
  while (true) {
    if (!fast || !fast.next) {
      return null
    }
    fast = fast.next.next
    slow = slow.next
    if (fast === slow) {
      break
    }
  }
  fast = head
  while (fast !== slow) {
    fast = fast.next
    slow = slow.next
  }
  return fast
};

Runtime: 56 ms, faster than 99.15% of JavaScript online submissions for Linked List Cycle II.

Memory Usage: 36.8 MB, less than 31.25% of JavaScript online submissions for Linked List Cycle II.

func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for true {
        if fast == nil || fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        slow = slow.Next
        if slow == fast {
            break
        }
    }
    fast = head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

Runtime: 8 ms, faster than 34.43% of Go online submissions for Linked List Cycle II.

Memory Usage: 3.7 MB, less than 50.00% of Go online submissions for Linked List Cycle II.