Detect Loop in Linked List

mediumSave

Linked ListTwo Pointers

Given the head of a singly linked list, write a function to determine if the linked list has a loop. A loop exists if a node's next points back to a previous node in the list. The function should return true if a loop is found and false otherwise.

Example 1

Input

[
  [
    3,
    2,
    0,
    -4
  ]
]

Output

true

Explanation. Setting the `next` pointer of the last node to point to the second node creats a loop, and hence the function returns `true`.

Example 2

Input

[
  [
    1,
    2
  ]
]

Output

false

Explanation. The linked list does not form a loop as no node points back to a previous node.

Example 3

Input

[
  [
    1
  ]
]

Output

false

Explanation. A single node not pointing to itself should return `false`.

Follow-up: Can you extend your solution to return the node where the loop starts?

Constraints:

- You must solve this problem in O(N) time complexity and O(1) space complexity.\n- The linked list will have at least one node.

Views: 3