"content":"summary_large_image"}],["$","meta","19",{"name":"twitter:title","content":"K5kC | Code & More"}],["$","meta","20",{"name":"twitter:description","content":"Practice coding problems, learn algorithms and data structures, and improve your programming skills with K5kC."}],["$","meta","21",{"name":"twitter:image","content":"https://k5kc.com/images/og-image.png"}]] 1e:I[34242,["/_next/static/chunks/5374600b61945acd.js","/_next/static/chunks/75bfb27789fc0b9a.js"],"default"] 1f:I[34263,["/_next/static/chunks/5374600b61945acd.js","/_next/static/chunks/75bfb27789fc0b9a.js"],"default"] 20:I[56081,["/_next/static/chunks/5374600b61945acd.js","/_next/static/chunks/75bfb27789fc0b9a.js"],"default"] 21:I[12820,["/_next/static/chunks/5374600b61945acd.js","/_next/static/chunks/75bfb27789fc0b9a.js"],"default"] 22:I[15024,["/_next/static/chunks/5374600b61945acd.js","/_next/static/chunks/75bfb27789fc0b9a.js"],"default"] 23:Td02,

Problem

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. If there is no cycle, return null.

Try solving it using constant additional space.

Definition - Circular Linked List

A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

This is extension of Linked List Cycle 1 - Detect Cycle

Examples

Example 1

Input: 
	head = [0, 1, 3, 2, 4]
output: 
	2
Explanation: Cycle starts at node 2

70%

Example 2

Input: 
	head = [1, 2, 3, 4, 5, 6]
output: 
	3
Explanation: Cycle starts at node 3

70%

Solution

Method 1 - Using Hashmap

In first iteration, we add all the elements to hashmap of <Node, Boolean>. Initially boolean value is false. Now there are 2 cases:

If we reach end of list, i.e. we get null, we return null as there is no cyle.
If we see repeating, that means we completed first cycle. We start setting the boolean value for node to true, marking it as part of cycle.
When we see the element in the list, and boolean value is true, that means we are entering second time, that means we are at the start of the cyc

Related Tags