Detect a loop in LL
HashedInThe 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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question