Linked list cycle
You get head, the first node of a linked list, or None if the list is empty. Each node is a ListNode with a value (node.val) and a link (node.next) to the node after it.
In a healthy list, following next from the head ends at None. In a broken one, the last node's next points back to an earlier node, or to itself, so following next goes around the same nodes forever. That loop is a cycle. Return True if the list has a cycle and False if it does not.
Examples describe a list by its values and pos, the position (counting from 0) of the node that the last node points back to. pos = -1 means there is no cycle. Your function receives only head.
values = [5, 1, 8, 2], pos = 1OutputTrueThe 2 points back to the 1, so the walk goes 5, 1, 8, 2, 1, 8, 2, and so on forever.
values = [4, 7], pos = 0OutputTrueThe 7 points back to the 4.
values = [6, 3, 9], pos = -1OutputFalseThe 9's next is None, so the walk ends.
0 ≤ number of nodes ≤ 104
-105 ≤ node value ≤ 105
posis -1 or a valid position in the list.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.