In this post we will solve the LeetCode 141 Linked List Cycle problem.
Given head, the head of a linked list, determine if the linked list has a cycle in it. 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. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false. Constraints: o The number of the nodes in the list is in the range [0, 10^4]. 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
We are given a singly linked list and are asked to determine if there is a cycle in it. If interested in the problem please take a look at the current description of it in the LeetCode website.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
}
}
The description of the function of interest is very adequate. We are given the `head` of the list and must return `true` if the linked list has a cycle or `false` if it does not.
In addition we are provided with the definition of the ListNode class which is 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 ListNode class.
I will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer. When I feel that I can submit the problem, I copy and paste the solution to the online IDE provided by LeetCode and submit it for verification.
I will need a simple test scaffold to develop the solution on my computer. Please note that the test scaffold IS NOT PART OF THE SOLUTION!
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 <<< hasCycle0: true main <<< hasCycle: true 1,2 0 main <<< arr: [1, 2] main <<< pos: 0 main <<< head: 1->2-> cycle detected @ p.val: 1 main <<< hasCycle0: true main <<< hasCycle: true 1 -1 main <<< arr: [1] main <<< pos: -1 main <<< head: 1 main <<< hasCycle0: false main <<< hasCycle: false 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 <<< hasCycle0: false main <<< hasCycle: false 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 <<< hasCycle0: true main <<< hasCycle: true 1,2,3,4,5,6,7 5 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< pos: 5 main <<< head: 1->2->3->4->5->6->7-> cycle detected @ p.val: 6 main <<< hasCycle0: true main <<< hasCycle: true 1,2,3,4,5,6,7 6 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< pos: 6 main <<< head: 1->2->3->4->5->6->7-> cycle detected @ p.val: 7 main <<< hasCycle0: true main <<< hasCycle: true 1,2,3,4,5,6,7 0 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< pos: 0 main <<< head: 1->2->3->4->5->6->7-> cycle detected @ p.val: 1 main <<< hasCycle0: true main <<< hasCycle: true
Test cases are separated by two blank lines.
The first line in each test represents the values for the nodes in the linked list. The second line contains the node with a cycle. Note that the second argument is used to generate the linked list and IS NOT PASSED to the function of interest.
Our test code reads the input lines and populates the int[] `arr` and the `pos` variable. The contents of the variables are then displayed to allow us to verify that all is well so far.
It seems that the test code populates and displays the linked list `head` which will be used as a single argument to the function of interest.
Please note that since the linked list may or may not contain a cycle based on the contents of the `pos` variable, when we display it we must check for cycles. This IS NOT PART OF THE SOLUTION, but if we do not, the attempt to display the list would loop indefinitely or we would have to specify a maximum number of nodes to display before the function exits. In this case it would be 10^4 nodes.
Our test scaffold then calls two implementations of the function of interest and displays the returned values.
/**
* Test scaffold
* !!! NOT PART OF SOLUTION !!!
*/
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 <<< hasCycle0: " + hasCycle0(head));
// **** invoke function of interest and display result ****
System.out.println("main <<< hasCycle: " + hasCycle(head));
}
This is the code for our test scaffold. Please note that it IS NOT PART OF THE SOLUTION!
The code reads the first two input lines. Extracts the associated values. It uses the contents of `arr` and `pos` to create the linked list. The linked list is displayed and two implementations of the function of interest are called and their respective values are displayed.
/**
* 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;
}
}
Since I am developing the solution on my computer, I also have to implement the ListNode class. For testing purposes I added the `toString` function. The implementation of the ListNode is provided to you by LeetCode when you solve the problem using their online IDE.
/**
* 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 function which IS NOT PART OF THE SOLUTION is used to populate the linked list with or without a cycle.
We start by performing sanity checks followed by initialization steps. The array is traversed building the linked list. Note that we need to know when the `cycle` node is created so we can maintain a reference to it to create the cycle in the linked list.
After the loop completes, we check if we have to create a cycle with the `tail` node. If needed we do so.
The `head` of the linked list is then returned.
/**
* 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 contents of the linked list. IT IS NOT PART OF THE SOLUTION. You might want to skip looking at the code until after we look at the first implementation of the function of interest. I should have moved this function towards the end of this post.
/**
* Given head, the head of a linked list,
* determine if the linked list has a cycle in it.
* Using a hash set.
*
* Runtime: O(n) - Space: O(n)
*
* Runtime: 4 ms, faster than 20.06% of Java online submission.
* Memory Usage: 39.1 MB, less than 99.82% of Java online submissions.
*
* 20 / 20 test cases passed.
* Status: Accepted
* Runtime: 4 ms
* Memory Usage: 39.1 MB
*/
static public boolean hasCycle0(ListNode head) {
// **** sanity checks ****
if (head == null || head.next == null) return false;
// **** initialization ****
HashSet<ListNode> hs = new HashSet<>();
// **** traverse the linked list looking for cycles ****
for (ListNode p = head; p != null; p = p.next) {
if (hs.add(p) == false) return true;
}
// **** cycle NOT found ****
return false;
}
In this implementation of the function of interest we will use a hash set to remember the nodes in the linked list. Let’s see how we use the hash set in this situation.
We start by performing sanity checks. We then initialize the hash set.
In the loop we traverse the linked list from head or until we can no longer proceed because we found the end of the linked list indicating that there is no cycle. As we traverse the linked list we add each node to the hash set. If a node is already in the hash set indicating we have already visited the node, we have a cycle so we return `true`.
Please take a look at the comments at the beginning of this function. It was accepted by LeetCode but it is somewhat slow and most importantly there must be a better way to implement the task at hand.
I did some quick searches on the web and found Floyd’s Cycle-Finding Algorithm
(https://en.wikipedia.org/wiki/Cycle_detection) which was designed for finding cycles. Let’s give it a try.
/**
* Given head, the head of a linked list,
* determine if the linked list has a cycle in it.
*
* Runtime: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 40 MB, less than 63.35% of Java online submissions.
*
* 20 / 20 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 40 MB
*/
static public boolean hasCycle(ListNode head) {
// **** sanity checks ****
if (head == null || head.next == null) return false;
// **** initialization ****
ListNode h = head;
ListNode t = head;
// **** traverse the linked list - O(n) ****
while (h != null && h.next != null) {
// **** move t & h forward ****
t = t.next; // single speed
h = h.next.next; // double speed
// **** check if we found a cycle ****
if (h == t) return true;
}
// **** no cycle found ****
return false;
}
As usual we start with sanity checks followed by initialization. In this case we will use two pointers named `h` for hare and `t` for turtle. Pointer `h` moves at double the speed (two nodes at a time) than pointer `t` which moves one node at a time. Perhaps I should have called one pointer `slow` and the other `fast`. Some implementations have used such nomenclature.
In the main loop we traverse the linked list making sure that `t` does not go over the possible end of the linked list. This takes into account the fact that the linked list might not contain a cycle.
On each step we move forward `t` and `h`. We then check if `h` equals `t`. If so we have found a cycle and return `true`.
After the exit the loop if no cycle has been detected, we return `false`.
This implementation uses two pointers.
Please take a look at the comments section of the function of interest. It seems that most people used different implementations based of Floyd’s Cycle-Finding Algorithm.
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 LinkedListCycle.
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