Detect the First Node of the Loop in a Singly Linked List

You are provided with a singly linked list that may contain a cycle. Your task is to return the node where the cycle begins, if such a cycle exists.

A cycle occurs if a node's next pointer points back to any preceding node in the list. This means the linked list will not have a distinct start and end but will cycle through a set of nodes.

Input:

The first line contains an integer ‘T’ that signifies the number of test cases. Each test case includes: The first line containing singly linked list elements, separated by a single space and ending with -1. Note that -1 is a terminator and not a list element. The second line includes an integer "pos" that indicates the 0-indexed position in the list where the tail connects back to form a cycle. If "pos" is -1, the linked list has no cycle.

Output:

For each test case, print the integer "pos" which indicates the 0-indexed position of the first node in the linked list that forms the cycle's start. Print -1 if there is no cycle in the linked list.

Example:

Input:
3
1 2 3 4 5 -1
-1
1 2 3 4 5 6 7 8 -1
2
1 -1
0
Output:
-1
2
0

Constraints:

  • 0 ≤ T ≤ 50
  • -104 ≤ N ≤ 104
  • -1 ≤ pos < N
  • -109 ≤ data ≤ 109 and data ≠ -1
  • Time Limit: 1 sec

Note:

Simply implement the function; output handling is predefined.

Follow-Up:

Can you solve this problem using O(N) time complexity and constant space?
AnswerBot
1y

To detect the first node of a cycle in a singly linked list, we can use the Floyd's Tortoise and Hare algorithm.

  • Use two pointers, slow and fast, to traverse the linked list.

  • If there is a cycle, the fa...read more

Help your peers!
Select
Add answer anonymously...

Popular interview questions of Program Associate

A Program Associate was asked Q1. What are the different types of cloud computing?
A Program Associate was asked Q2. What are Cloud Deployment models?
A Program Associate was asked Q3. What is cloud computing?

Top HR questions asked in Wells Fargo Program Associate

A Program Associate was asked 6mo agoQ1. What will you do if your teammate is not following the process?
A Program Associate was asked 6mo agoQ2. What was the toughest challenge you've overcome?
A Program Associate was asked 10mo agoQ3. What was your crucial role in the project contribution?
Wells Fargo Program Associate Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits