Detect a loop in LL
The problem
Given the head of a singly linked list. Return true if a loop exists in the linked list or return false.
A loop exists in a linked list if some node in the list can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index(0-based) of the node from where the loop starts. Note that pos is not passed as a parameter.
Input: head -> 1 -> 2 -> 3 -> 4 -> 5, pos = 1 Output: true Explanation: The tail of the linked list connects to the node at 1st index.
Input: head -> 1 -> 3 -> 7 -> 4, pos = -1 Output: false Explanation: No loop is present in the linked list.
Input: head -> 6 -> 3 -> 7, pos = 0
- 0 <= number of nodes in the cycle <= 105
- 0 <= ListNode.val <= 104
- pos is -1 or a valid index in the linked list
cpp
/*
Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
}
};java
/*Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
*/
class Solution {
public boolean hasCycle(ListNode head) {
}
}python
# Definition of singly linked list:
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head):javascript
/*Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
*/
class Solution {
hasCycle(head) {
}
}csharp
/* Definition for singly-linked list.
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
*/
public class Solution {
public bool HasCycle(ListNode head) {
}
}go
/*
Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
*/
func HasCycle(head *ListNode) bool {
}Stuck? Show a way to structure it+
- 01Initialize both pointers at head
- 02Advance fast only when fast and fast.next exist
- 03Compare pointers after movement
- 04Return true on a meeting and false at null
Reference answer
Then expect these follow-ups
How do you find the cycle entry?
Tests: follow-up reasoning
What is the proof that pointers meet?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question