LeetCode 142 Linked List Cycle II in Java

In this post I will be solving LeetCode 142 Linked List Cycle II using the Java programming language.

This problem seems to be the continuation of a problem we solved earlier LeetCode 141 Linked List Cycle in Java in this blog. Perhaps you would like to read it before attempting to solve the problem in this post.

Given the head of a linked list, 
return the node where the cycle begins.
If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that 
can be reached again by continuously following the next pointer. 

Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed).
It is -1 if there is no cycle.
Note that pos is not passed as a parameter.

Do not modify the linked list.


o The number of the nodes in the list is in the range [0, 104].
o -10^5 <= Node.val <= 10^5
o pos is -1 or a valid index in the linked-list.

Related Topics:

o Hash Table
o Linked List
o Two Pointers

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

We are given a singly linked list which may or may not have a cycle. We need to return `null` if it does not contain a cycle, or the node where the cycle begins. The LeetCode web site contains some diagrams to better illustrate the linked lists with a cycle. Continue reading “LeetCode 142 Linked List Cycle II in Java”