Skip to main content

Detect cycle in a linked list in linear time

Here given code implementation process.

/*
  Java program
  Detect cycle in a linked list in linear time
*/
import java.util.Set;
import java.util.HashSet;

// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}

public class LoopDetection
{
    // Check whether given linked list contains loop or not
    public void findLoop(LinkNode head)
    {
        // Use to collect unique nodes
        Set<LinkNode> result = new HashSet<LinkNode>();

        // Loop indicators
        Boolean status = false;

        // Start with first node
        LinkNode node = head;

        // iterate linked list nodes
        while (node != null && status == false)
        {
            if (result.contains(node))
            {
                status = true;
            }
            else
            {
                // Display node value
                System.out.print("  " + (node.data));
                // Add node
                result.add(node);
            }
            // Visit to next node
            node = node.next;
        }
        if (status == true)
        {
            System.out.print("\n  Loop are exist\n");
        }
        else
        {
            System.out.print("\n  Loop are not exist\n");
        }
    }
    public static void main(String[] args)
    {
        LoopDetection task = new LoopDetection();
       
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        head.next.next.next.next.next = new LinkNode(6);
        // 1 → 2 → 3 → 4 → 5 → 6 → NULL
        task.findLoop(head);
        // Create a loop 
        head.next.next.next.next.next.next = head.next.next;
        
        // 1 → 2 → 3 → 4 → 5 → 6 ──┐
        //         └───────────────┘                 
        // Test
        task.findLoop(head);
    }
}

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
// Include header file
#include <iostream>
#include <set>
using namespace std;

// Linked list node
class LinkNode
{
	public: int data;
	LinkNode *next;
	LinkNode(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class LoopDetection
{
	public:
		// Check whether given linked list contains loop or not
		void findLoop(LinkNode *head)
		{
			// Use to collect unique nodes
			set <LinkNode*> result;
			// Loop indicators
			bool status = false;
			// Start with first node
			LinkNode *node = head;
			// iterate linked list nodes
			while (node != NULL && status == false)
			{
				if (result.find(node) != result.end())
				{
					status = true;
				}
				else
				{
					// Display node value
					cout << "  " << (node->data);
					result.insert(node);
				}
				// Visit to next node
				node = node->next;
			}
			if (status == true)
			{
				cout << "\n  Loop are exist\n";
			}
			else
			{
				cout << "\n  Loop are not exist\n";
			}
		}
};
int main()
{
	LoopDetection task = LoopDetection();
	LinkNode *head = new LinkNode(1);
	head->next = new LinkNode(2);
	head->next->next = new LinkNode(3);
	head->next->next->next = new LinkNode(4);
	head->next->next->next->next = new LinkNode(5);
	head->next->next->next->next->next = new LinkNode(6);
	// 1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head);
	// Create a loop
	head->next->next->next->next->next->next = head->next->next;
	// 1 → 2 → 3 → 4 → 5 → 6 ──┐
	//         └───────────────┘
	// Test
	task.findLoop(head);
	return 0;
}

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
// Include namespace system
using System;
using System.Collections.Generic;
/*
  C# program
  Detect cycle in a linked list in linear time
*/
// Linked list node
public class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class LoopDetection
{
	// Check whether given linked list contains loop or not
	public void findLoop(LinkNode head)
	{
		// Use to collect unique nodes
		HashSet < LinkNode > result = new HashSet < LinkNode > ();
		// Loop indicators
		Boolean status = false;
		// Start with first node
		LinkNode node = head;
		// iterate linked list nodes
		while (node != null && status == false)
		{
			if (result.Contains(node))
			{
				status = true;
			}
			else
			{
				// Display node value
				Console.Write("  " + (node.data));
				result.Add(node);
			}
			// Visit to next node
			node = node.next;
		}
		if (status == true)
		{
			Console.Write("\n  Loop are exist\n");
		}
		else
		{
			Console.Write("\n  Loop are not exist\n");
		}
	}
	public static void Main(String[] args)
	{
		LoopDetection task = new LoopDetection();
		LinkNode head = new LinkNode(1);
		head.next = new LinkNode(2);
		head.next.next = new LinkNode(3);
		head.next.next.next = new LinkNode(4);
		head.next.next.next.next = new LinkNode(5);
		head.next.next.next.next.next = new LinkNode(6);
		// 1 → 2 → 3 → 4 → 5 → 6 → NULL
		task.findLoop(head);
		// Create a loop
		head.next.next.next.next.next.next = head.next.next;
		// 1 → 2 → 3 → 4 → 5 → 6 ──┐
		//         └───────────────┘
		// Test
		task.findLoop(head);
	}
}

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
<?php
/*
  Php program
  Detect cycle in a linked list in linear time
*/
// Linked list node
class LinkNode
{
	public $data;
	public $next;

	function __construct($data)
	{
		$this->data = $data;
		$this->next = null;
	}
}
class LoopDetection
{
	// Check whether given linked list contains loop or not
	public	function findLoop($head)
	{
		// Use to collect unique nodes
		$result = array();
		// Loop indicators
		$status = false;
		// Start with first node
		$node = $head;
		// iterate linked list nodes
		while ($node != null && $status == false)
		{
			if (($key = array_search($node, $result) !== false))
			{
				$status = true;
			}
			else
			{
				// Display node value
				echo "  ". ($node->data);
				$result[] = $node;
			}
			// Visit to next node
			$node = $node->next;
		}
		if ($status == true)
		{
			echo "\n  Loop are exist\n";
		}
		else
		{
			echo "\n  Loop are not exist\n";
		}
	}
}

function main()
{
	$task = new LoopDetection();
	$head = new LinkNode(1);
	$head->next = new LinkNode(2);
	$head->next->next = new LinkNode(3);
	$head->next->next->next = new LinkNode(4);
	$head->next->next->next->next = new LinkNode(5);
	$head->next->next->next->next->next = new LinkNode(6);
	// 1 → 2 → 3 → 4 → 5 → 6 → NULL
	$task->findLoop($head);
	// Create a loop
	$head->next->next->next->next->next->next = $head->next->next;
	// 1 → 2 → 3 → 4 → 5 → 6 ──┐
	//         └───────────────┘
	// Test
	$task->findLoop($head);
}
main();

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
/*
  Node Js program
  Detect cycle in a linked list in linear time
*/
// Linked list node
class LinkNode
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class LoopDetection
{
	// Check whether given linked list contains loop or not
	findLoop(head)
	{
		// Use to collect unique nodes
		var result = new Set();
		// Loop indicators
		var status = false;
		// Start with first node
		var node = head;
		// iterate linked list nodes
		while (node != null && status == false)
		{
			if (result.has(node))
			{
				status = true;
			}
			else
			{
				// Display node value
				process.stdout.write("  " + (node.data));
				result.add(node);
			}
			// Visit to next node
			node = node.next;
		}
		if (status == true)
		{
			process.stdout.write("\n  Loop are exist\n");
		}
		else
		{
			process.stdout.write("\n  Loop are not exist\n");
		}
	}
}

function main()
{
	var task = new LoopDetection();
	var head = new LinkNode(1);
	head.next = new LinkNode(2);
	head.next.next = new LinkNode(3);
	head.next.next.next = new LinkNode(4);
	head.next.next.next.next = new LinkNode(5);
	head.next.next.next.next.next = new LinkNode(6);
	// 1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head);
	// Create a loop
	head.next.next.next.next.next.next = head.next.next;
	// 1 → 2 → 3 → 4 → 5 → 6 ──┐
	//         └───────────────┘
	// Test
	task.findLoop(head);
}
main();

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
#   Python 3 program
#   Detect cycle in a linked list in linear time

#  Linked list node
class LinkNode :
	
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class LoopDetection :
	#  Check whether given linked list contains loop or not
	def findLoop(self, head) :
		#  Use to collect unique nodes
		result = set()
		#  Loop indicators
		status = False
		#  Start with first node
		node = head
		#  iterate linked list nodes
		while (node != None and status == False) :
			if (node in result) :
				status = True
			else :
				#  Display node value
				print(" ", (node.data), end = "")
				#  Add node
				result.add(node)
			
			#  Visit to next node
			node = node.next
		
		if (status == True) :
			print("\n  Loop are exist")
		else :
			print("\n  Loop are not exist")
		
	

def main() :
	task = LoopDetection()
	head = LinkNode(1)
	head.next = LinkNode(2)
	head.next.next = LinkNode(3)
	head.next.next.next = LinkNode(4)
	head.next.next.next.next = LinkNode(5)
	head.next.next.next.next.next = LinkNode(6)
	#  1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head)
	#  Create a loop 
	head.next.next.next.next.next.next = head.next.next
	#  1 → 2 → 3 → 4 → 5 → 6 ──┐
	#          └───────────────┘                 
	#  Test
	task.findLoop(head)

if __name__ == "__main__": main()

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
#   Ruby program
#   Detect cycle in a linked list in linear time

#  Linked list node
class LinkNode  
	# Define the accessor and reader of class LinkNode  
	attr_reader :data, :next
	attr_accessor :data, :next
 
	def initialize(data) 
		self.data = data
		self.next = nil
	end
end

class LoopDetection 
	#  Check whether given linked list contains loop or not
	def findLoop(head) 
		#  Use to collect unique nodes
		result = []
		#  Loop indicators
		status = false
		#  Start with first node
		node = head
		#  iterate linked list nodes
		while (node != nil && status == false) 
			if (result.include?(node)) 
				status = true
			else 
				#  Display node value
				print("  ", (node.data))
				result.push(node)
			end

			#  Visit to next node
			node = node.next
		end

		if (status == true) 
			print("\n  Loop are exist\n")
		else 
			print("\n  Loop are not exist\n")
		end

	end

end

def main() 
	task = LoopDetection.new()
	head = LinkNode.new(1)
	head.next = LinkNode.new(2)
	head.next.next = LinkNode.new(3)
	head.next.next.next = LinkNode.new(4)
	head.next.next.next.next = LinkNode.new(5)
	head.next.next.next.next.next = LinkNode.new(6)
	#  1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head)
	#  Create a loop 
	head.next.next.next.next.next.next = head.next.next
	#  1 → 2 → 3 → 4 → 5 → 6 ──┐
	#          └───────────────┘                 
	#  Test
	task.findLoop(head)
end

main()

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist

import scala.collection.mutable._;
/*
  Scala program
  Detect cycle in a linked list in linear time
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class LoopDetection
{
	// Check whether given linked list contains loop or not
	def findLoop(head: LinkNode): Unit = {
		// Use to collect unique nodes
		var result: Set[LinkNode] = Set();
		// Loop indicators
		var status: Boolean = false;
		// Start with first node
		var node: LinkNode = head;
		// iterate linked list nodes
		while (node != null && status == false)
		{
			if (result.contains(node))
			{
				status = true;
			}
			else
			{
				// Display node value
				print("  " + (node.data));
				result.add(node);
			}
			// Visit to next node
			node = node.next;
		}
		if (status == true)
		{
			print("\n  Loop are exist\n");
		}
		else
		{
			print("\n  Loop are not exist\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LoopDetection = new LoopDetection();
		var head: LinkNode = new LinkNode(1);
		head.next = new LinkNode(2);
		head.next.next = new LinkNode(3);
		head.next.next.next = new LinkNode(4);
		head.next.next.next.next = new LinkNode(5);
		head.next.next.next.next.next = new LinkNode(6);
		// 1 → 2 → 3 → 4 → 5 → 6 → NULL
		task.findLoop(head);
		// Create a loop
		head.next.next.next.next.next.next = head.next.next;
		// 1 → 2 → 3 → 4 → 5 → 6 ──┐
		//         └───────────────┘
		// Test
		task.findLoop(head);
	}
}

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
/*
  Swift 4 program
  Detect cycle in a linked list in linear time
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class LoopDetection
{
	// Check whether given linked list contains loop or not
	func findLoop(_ head: LinkNode? )
	{
		// Use to collect unique nodes
		var result = [LinkNode]()
		// Loop indicators
		var status: Bool? = false;
		// Start with first node
		var node: LinkNode? = head;
		// iterate linked list nodes
		while (node  != nil && status == false)
		{
			if (result.contains(where: {$0 === node}))
			{
				status = true;
			}
			else
			{
				// Display node value
				print("  ", (node!.data), terminator: "");
				result.append(node!);
			}
			// Visit to next node
			node = node!.next;
		}
		if (status == true)
		{
			print("\n  Loop are exist");
		}
		else
		{
			print("\n  Loop are not exist");
		}
	}
}
func main()
{
	let task: LoopDetection = LoopDetection();
	let head: LinkNode? = LinkNode(1);
	head!.next = LinkNode(2);
	head!.next!.next = LinkNode(3);
	head!.next!.next!.next = LinkNode(4);
	head!.next!.next!.next!.next = LinkNode(5);
	head!.next!.next!.next!.next!.next = LinkNode(6);
	// 1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head);
	// Create a loop
	head!.next!.next!.next!.next!.next!.next = head!.next!.next;
	// 1 → 2 → 3 → 4 → 5 → 6 ──┐
	//         └───────────────┘
	// Test
	task.findLoop(head);
}
main();

Output

   1   2   3   4   5   6
  Loop are not exist
   1   2   3   4   5   6
  Loop are exist
/*
  Kotlin program
  Detect cycle in a linked list in linear time
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class LoopDetection
{
	// Check whether given linked list contains loop or not
	fun findLoop(head: LinkNode ? ): Unit
	{
		// Use to collect unique nodes
		var result: MutableSet <LinkNode> = mutableSetOf <LinkNode> ();
		// Loop indicators
		var status: Boolean ? = false;
		// Start with first node
		var node: LinkNode ? = head;
		// iterate linked list nodes
		while (node != null && status == false)
		{
			if (result.contains(node))
			{
				status = true;
			}
			else
			{
				// Display node value
				print("  " + (node.data));
				result.add(node);
			}
			// Visit to next node
			node = node.next;
		}
		if (status == true)
		{
			print("\n  Loop are exist\n");
		}
		else
		{
			print("\n  Loop are not exist\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: LoopDetection = LoopDetection();
	var head: LinkNode = LinkNode(1);
	head.next = LinkNode(2);
	head.next?.next = LinkNode(3);
	head.next?.next?.next = LinkNode(4);
	head.next?.next?.next?.next = LinkNode(5);
	head.next?.next?.next?.next?.next = LinkNode(6);
	// 1 → 2 → 3 → 4 → 5 → 6 → NULL
	task.findLoop(head);
	// Create a loop
	head.next?.next?.next?.next?.next?.next = head.next?.next;
	// 1 → 2 → 3 → 4 → 5 → 6 ──┐
	//         └───────────────┘
	// Test
	task.findLoop(head);
}

Output

  1  2  3  4  5  6
  Loop are not exist
  1  2  3  4  5  6
  Loop are exist
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment