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. Constraints: 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.
We will work on two implementations. One that does not use constant memory and the other which does.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
}
}
The signature for the function of interest matches the requirements nicely. We are provided the `head` of the linked list and must return `null` if there is no cycle, or the node in which the cycle begins.
In addition we are given the description of the `ListNode` class which is used to represent the nodes in the linked list.
Since I will be solving the problem using Java and the VSCode IDE on a Windows computer, I will need a simple test scaffold. If you use the online IDE provided by LeetCode you will not need to develop test code.
1,2,3,4,5,6,7 -1 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< pos: -1 main <<< head: 1->2->3->4->5->6->7 main <<< detectCycle0: null <<< h: 7 h.next: null main <<< detectCycle: null 1,2,3,4,5,6,7 3 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< pos: 3 main <<< head: 1->2->3->4->5->6->7-> cycle detected @ p.val: 4 main <<< detectCycle0: 4 <<< h: 5 h.next: 6 <<< h: 1 t: 5 <<< h: 2 t: 6 <<< h: 3 t: 7 <<< h: 4 t: 4 main <<< detectCycle: 4 3,2,0,-4 1 main <<< arr: [3, 2, 0, -4] main <<< pos: 1 main <<< head: 3->2->0->-4-> cycle detected @ p.val: 2 main <<< detectCycle0: 2 <<< h: -4 h.next: 2 <<< h: 3 t: -4 <<< h: 2 t: 2 main <<< detectCycle: 2 1,2 0 main <<< arr: [1, 2] main <<< pos: 0 main <<< head: 1->2-> cycle detected @ p.val: 1 main <<< detectCycle0: 1 <<< h: 1 h.next: 2 <<< h: 1 t: 1 main <<< detectCycle: 1 1 -1 main <<< arr: [1] main <<< pos: -1 main <<< head: 1 main <<< detectCycle0: null main <<< detectCycle: null 1 0 main <<< arr: [1] main <<< pos: 0 main <<< head: 1-> cycle detected @ p.val: 1 main <<< detectCycle0: 1 main <<< detectCycle: 1
Each test case is separated by two blank lines.
The first line of each test case contains the values for the nodes in the linked list. The second input line contains the value `pos` which indicates the position of the node in the linked list in which the cycle begins. This value is provided so we can better understand the topology of the linked list.
Our test code seems to read in the first two input lines, populate the associated variables and then display their values. This is done so we can verify that all is well so far.
It seems that our test code populates the linked list with the values provided by the `arr` int[] array. The linked list is then displayed. All seems to be going well so far.
The test code then makes calls to two implementations of the function of interest. The second implementation seems to display some values to help us understand what is going on. Such a display IS NOT PART OF THE SOLUTION. We need to remove the `println` statements when submitting our code for evaluation on the LeetCode website.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reder ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and split node values ****
String[] strs = br.readLine().trim().split(",");
// **** read `pos` ****
int pos = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// **** convert string array to integer array ****
int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< pos: " + pos);
// **** populate linked list ****
ListNode head = populate(arr, pos);
// ???? ????
System.out.println("main <<< head: " + display(head));
// **** invoke function of interest and display result ****
System.out.println("main <<< detectCycle0: " + detectCycle0(head));
// **** invoke function of interest and display result ****
System.out.println("main <<< detectCycle: " + detectCycle(head));
}
This is the test code I used to develop the solution. Please note that the test scaffold IS NOT PART OF THE SOLUTION!
The code seems to follow closely the description of the test cases. I believe there is not much to add at this time.
/**
* Class for nodes in the linked list.
*/
static class ListNode {
// **** members ****
int val;
ListNode next;
// **** constructor(s) ****
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// **** ****
@Override
public String toString() {
return "" + this.val;
}
}
This is the implementation of the ListNode class used to represent the nodes in the linked list. If you solve the problem using the online IDE provided by LeetCode you will not need to implement the class.
/**
* Populate linked list from the contents of the specified array.
*
* !!! NOT PART OF SOLUTION !!!
*/
static ListNode populate(int[] arr, int pos) {
// **** sanity ckeck(s) ****
if (arr.length == 0) return null;
// **** initialization ****
ListNode head = null;
ListNode cycle = null;
ListNode tail = null;
// **** traverse array adding nodes to the linked list ****
for (int i = arr.length - 1; i >= 0; i--) {
// **** update head of list ****
head = new ListNode(arr[i], head);
// **** update tail of list ****
if (tail == null) tail = head;
// **** save node at specified position ****
if (pos == i) cycle = head;
}
// **** generate cycle ****
if (cycle != null) tail.next = cycle;
// **** return head of linked list ****
return head;
}
This is the function I used to populate the linked list. This code IS NOT PART OF THE SOLUTION. Note that the `pos` argument provides the function with the position of the node in the linked list where the cycle begins. Such value may be set to -1 indicating that the linked list does not contain a cycle.
/**
* Display linked list.
* Stops after last node or cycle detected.
*
* !!! NOT PART OF SOLUTION !!!
*/
static String display(ListNode head) {
// **** sanity check(s) ****
if (head == null) return "";
// **** initialization ****
StringBuilder sb = new StringBuilder();
HashSet<ListNode> hs = new HashSet<ListNode>();
// **** traverse link list ****
for (ListNode p = head; p != null; p = p.next) {
// **** add this node to the hash set ****
if (hs.add(p) == false) {
sb.append(" cycle detected @ p.val: " + p.val);
break;
}
// **** append node value to string builder ****
sb.append(p.val);
if (p.next != null)
sb.append("->");
}
// **** return string representation of linked list ****
return sb.toString();
}
This function is used to display the nodes in a linked list with or without cycles. This function IS NOT PART OF THE SOLUTION! I like to follow a Test Driven Development approach so I like to verify how things are progressing. I prefer to solve the problems as they develop rather than debugging the entire code at once.
At this time I will not go into much details for the function. It has to detect cycles to be usable. It uses a similar approach as the first implementation of the function of interest.
/**
* Given the head of a linked list,
* return the node where the cycle begins.
* If there is no cycle, return null.
*
* Runtime: O(n) - Space: O(n)
*
* Runtime: 3 ms, faster than 24.16% of Java online submissions.
* Memory Usage: 39.9 MB, less than 30.58% of Java online submissions.
*/
static public ListNode detectCycle0(ListNode head) {
// **** sanity check(s) ****
if (head == null || head.next == null) return null;
if (head.next == head) return head;
// **** initialization ****
HashSet<ListNode> hs = new HashSet<>();
// **** traverse the linked list detecting cycle ****
for (ListNode p = head; p != null; p = p.next) {
// **** check if cycle found at thsi node ****
if (hs.add(p) == false) return p;
}
// **** no cycle ****
return null;
}
This is the first implementation of the function of interest.
We start with some sanity checks and initializing a hash set.
The loop is used to traverse the linked list. At each pass we add the current node to the hash set. If the node is already in the hash set a cycle has been detected.
If we are able to complete the loop, then the linked list lacks a cycle and we return `null` to indicate so to the caller.
If you take a look at the comments section you can see that the solution was accepted by LeetCode but the execution time needs some work. There is a high percentage of solutions that run faster. They probably use the Floyd’s Cycle-Finding Algorithm.
/**
* Given the head of a linked list,
* return the node where the cycle begins.
* If there is no cycle, return null.
*
* Using Floyd’s Cycle-Finding Algorithm.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.8 MB, less than 86.49% of Java online submissions.
*
* 16 / 16 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.8 MB
*/
static public ListNode detectCycle(ListNode head) {
// **** sanity check(s) ****
if (head == null || head.next == null) return null;
if (head.next == head) return head;
// **** initialization ****
ListNode t = head; // tortoise at start of linked list
ListNode h = head; // hare at start of linked list
// **** traverse the linked list ****
while (h != null && h.next != null) {
// **** move h & t forward ****
h = h.next.next; // use double speed
t = t.next; // use single speed
// **** we encounter a cycle ****
if (t == h) break;
}
// ???? ????
System.out.println("<<< h: " + h + " h.next: " + h.next);
// **** check if linked list does NOT contain a cycle ****
if (h == null || h.next == null) return null;
// **** set h at head of linked list ****
h = head;
// **** move h & t forward at single speed ****
while (h != t) {
// ???? ????
System.out.println("<<< h: " + h + " t: " + t);
// **** move pointers forward (both at single speed) ****
t = t.next; // single speed
h = h.next; // single speed
}
// ???? ????
System.out.println("<<< h: " + h + " t: " + t);
// **** h and t at the cycle node ****
return h;
}
The implementation of the function of interest starts with some sanity checks filled by the initialization steps.
As with the previous post in this blog LeetCode 141 Linked List Cycle in Java, the first step is to define two pointers (references) that are used to traverse the linked list. Both start at the `head` element.
In the while loop we traverse the linked list with `t` (the slow turtle) moving forward one step at a time, and `h` (the fast hare) moving two steps at a time. Note that we use `h` to traverse the linked list because it will reach the end of the linked list (linked list does not have a cycle) first. We also need a check to see if `t` catches up with `h`, which is only possible if the linked list has a cycle.
After the loop exists we check if we did not encounter a cycle.
Now we need to find the node at which the cycle starts. For this we reset the `h` pointer to the head of the linked list and enter a second while loop. In this case we move both pointers forward at the same single speed. When the pointers meet we have found the node when the cycle starts so we exit the loop.
We then return the value of either pointer since both are pointing to the same node.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LinkedListCycleII.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John