142. Circular linked List II

Difficulty: medium

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.

** Does not allow modification of a given linked list.

Advanced:

  • Can you use itO(1)Space to solve this problem?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: returns a list node with index 0.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: returns NULL Explanation: There are no loops in the linked list.Copy the code

Tip:

  • The number of nodes in a linked list ranges from[0, 10<sup>4</sup>] 内
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
  • posThe value of- 1Or a valid index in a linked list

Solution

Language: java

Public class Solution {public ListNode detectCycle (ListNode head) {/ / HashSet if on the first (head = = null | | head. The next = = null) return null; Set<ListNode> set = new HashSet(); ListNode current = head; while(current ! = null) { if(! set.add(current)) { return current; } current = current.next; } return null; }}Copy the code

  • That’s a little inefficient, and they want space order 1.