Does the Linked List Loop
You are given head, the first node of a singly linked list. Each node has a value val and a link next.
In a normal list, the last node has next set to null (None in Python). In a list with a loop, the last node links back to an earlier node (or to itself), so following next never reaches null.
Return true if the list has a loop, and false if it does not. An empty list (head is null) has no loop.
Note
- Two different nodes can hold the same value. Compare nodes, not values.
- Do not change the list.
How the input is shown
A case is written as [values, pos]. values are the node values from the first node. pos is the index of the node that the last node links back to, or -1 if there is no loop. For example, [[5, 1, 8], 1] is 5 -> 1 -> 8, and the node with 8 links back to the node with 1. Your function gets only head; it does not get pos.
Hint: use two pointers. Move one pointer by one node and the other by two nodes at each step. If there is a loop, the fast pointer catches up with the slow one. If the fast pointer reaches null, there is no loop. This needs O(1) extra memory.
Examples
Example 1
- Input:
- [[5,1,8,1],2]
- Output:
- true
The list is 5 -> 1 -> 8 -> 1, and the last node links back to the node at index 2 (value 8). So the walk goes 8 -> 1 -> 8 -> 1 for ever.
Example 2
- Input:
- [[6,3,6],-1]
- Output:
- false
pos is -1, so the last node links to null. The value 6 appears twice, but these are two different nodes, so there is no loop.
Example 3
- Input:
- [[9],0]
- Output:
- true
There is one node, and its next link points to itself.
Constraints
- The list has
0to60nodes. 0 <= val <= 9posis-1or a valid index in the list (posis-1when the list is empty).
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.