Spired by fast and slow pointers


  • 0
    J

    The idea is to have two pointers that will traverse the whole list. The slow pointer will go one step a time, while the fast pointer will go two steps. If there's a cycle, there will be a time these two pointers will meet. Since we are not allowed to use extra space, so use recursion. Not sure if others come up with this idea.

        public static boolean hasCycle(ListNode slow, ListNode fast) {
            if (fast == null) {
                return false;
            } else if (fast == slow) {
                return true;
            } else {
                if (fast.next != null) {
                    return hasCycle(slow.next, fast.next.next);
                } else {
                    return hasCycle(slow.next, fast.next);
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.