Find loop node in linked list

In singly linked list, last node next field contains null value. That is indicate end of linked list. But in case this field are not null, that means linked list contain a loop. Our goal is to find this node which is create loop. In other words, find last node of linked list which is contain loop or creating a loop.

Here given code implementation process.

//C Program
//Find loop node in linked list
#include <stdio.h>
 //for malloc function
#include <stdlib.h>

//Create structure
struct Node
{
	int data;
	struct Node *next;
};
//Add new node at end of linked list 
void insert(struct Node **head, int value)
{
	//Create dynamic node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		node->data = value;
		node->next = NULL;
		if ( *head == NULL)
		{
			*head = node;
		}
		else
		{
			struct Node *temp = *head;
			//find last node
			while (temp->next != NULL)
			{
				temp = temp->next;
			}
			//add node at last possition
			temp->next = node;
		}
	}
}
//Display linked list element
void display(struct Node *head)
{
	if (head == NULL)
	{
		printf("Empty linked list");
	}
	struct Node *temp = head;
	while (temp != NULL)
	{
		printf("  %d", temp->data);
		temp = temp->next;
		if (temp == head)
		{
			return;
		}
	}
}
//Find loop node in given linked list
struct Node *find_loop_node(struct Node *temp, struct Node **result)
{
	if (temp == NULL || temp->next == NULL)
	{
		return temp;
	}
	else if (temp->next->next == NULL)
	{
		// When get node in loop
		// In case loop are not exist then result is null
		*result = temp;
		return temp;
	}
	//Get current node
	struct Node *current_node = temp->next;
	//important to control recursion
	temp->next = NULL;
	temp->next = find_loop_node(current_node, result);
	return temp;
}
// Handles the request of detect and find loop node in linked list
void loop_node(struct Node *head)
{
	if (head == NULL)
	{
		printf("Empty Linked List\n");
		return;
	}
	int status = 0;
	//Variable which is used to detect loop in linked list
	struct Node *first = head, *second = head;
	//Check that loop exists in given linked list or not
	while (second != NULL && second->next != NULL && second->next->next != NULL && status == 0)
	{
		first = first->next;
		second = second->next->next;
		if (first == second)
		{
			//loop is found
			status = 1;
		}
	}
	if (status == 1)
	{
		//When loop is exists in linked list
		struct Node *result = NULL;
		find_loop_node(head, &result);
		printf("\n  Loop Node is : %d\n", result->data);
	}
	else
	{
		printf("\n  Loop not exist\n");
	}
}
int main()
{
	//create node pointer
	struct Node *head = NULL;
	//Add linked list elements
	insert( &head, 7);
	insert( &head, 6);
	insert( &head, 2);
	insert( &head, 5);
	insert( &head, 9);
	insert( &head, 4);
	insert( &head, 8);
	insert( &head, 3);
	//Before contains loop
	display(head);
	//Create loop
	head->next->next->next->next->next->next->next->next = head->next->next;
	loop_node(head);
	return 0;
}

Output

  7  6  2  5  9  4  8  3
  Loop Node is : 3
//Java Program
//Find modular node in a linked list (from end of linked list)
//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node result;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.result = null;
	}
	//insert element
	public void insert(int data)
	{
		//Create  node
		Node node = new Node(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			Node temp = this.head;
			//find last node
			while (temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = node;
		}
	}
	//Display linked list nodes
	public void display()
	{
		if (this.head != null)
		{
			System.out.print(" Linked List :");
			Node temp = this.head;
			while (temp != null)
			{
				System.out.print(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					return;
				}
			}
		}
		else
		{
			System.out.println("Empty Linked List");
		}
	}
	//Find loop node in given linked list
	public Node find_loop_node(Node temp)
	{
		if (temp == null || temp.next == null)
		{
			return temp;
		}
		else if (temp.next.next == null)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			this.result = temp;
			return temp;
		}
		//Get current node
		Node current_node = temp.next;
		//important to control recursion
		temp.next = null;
		temp.next = find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	public void loop_node()
	{
		if (this.head == null)
		{
			System.out.print("Empty Linked List\n");
			return;
		}
		boolean status = false;
		//Variable which is used to detect loop in linked list
		Node first = this.head;
		Node second = this.head;
		//Check that loop exists in given linked list or not
		while (second != null && second.next != null && second.next.next != null && status == false)
		{
			first = first.next;
			second = second.next.next;
			if (first == second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			this.result = null;
			find_loop_node(this.head);
			System.out.print("\n Loop Node is : " + result.data + "\n");
		}
		else
		{
			System.out.print("\n Loop not exist\n");
		}
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(7);
		obj.insert(6);
		obj.insert(2);
		obj.insert(5);
		obj.insert(9);
		obj.insert(4);
		obj.insert(8);
		obj.insert(3);
		//Display all node
		obj.display();
		//Create loop
		obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;
		//Test Case
		obj.loop_node();
	}
}

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
//Include header file
#include <iostream>
using namespace std;

//C++ Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node
{
	public: 
    int data;
	Node * next;
	Node(int data)
	{
		//set node value
		this->data = data;
		this->next = NULL;
	}
};
class MyLinkedList
{
	public: 
    Node * head;
	Node * result;
	//Class constructors
	MyLinkedList()
	{
		this->head = NULL;
		this->result = NULL;
	}
	//insert element
	void insert(int data)
	{
		//Create  node
		Node * node = new Node(data);
		if (this->head == NULL)
		{
			this->head = node;
		}
		else
		{
			Node * temp = this->head;
			//find last node
			while (temp->next != NULL)
			{
				temp = temp->next;
			}
			temp->next = node;
		}
	}
	//Display linked list nodes
	void display()
	{
		if (this->head != NULL)
		{
			cout << " Linked List :";
			Node * temp = this->head;
			while (temp != NULL)
			{
				cout << " " << temp->data;
				temp = temp->next;
				if (temp == this->head)
				{
					return;
				}
			}
		}
		else
		{
			cout << "Empty Linked List";
		}
	}
	//Find loop node in given linked list
	Node * find_loop_node(Node * temp)
	{
		if (temp == NULL || temp->next == NULL)
		{
			return temp;
		}
		else if (temp->next->next == NULL)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			this->result = temp;
			return temp;
		}
		//Get current node
		Node * current_node = temp->next;
		//important to control recursion
		temp->next = NULL;
		temp->next = this->find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	void loop_node()
	{
		if (this->head == NULL)
		{
			cout << "Empty Linked List\n";
			return;
		}
		bool status = false;
		//Variable which is used to detect loop in linked list
		Node * first = this->head;
		Node * second = this->head;
		//Check that loop exists in given linked list or not
		while (second != NULL && second->next != NULL && second->next->next != NULL && status == false)
		{
			first = first->next;
			second = second->next->next;
			if (first == second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			this->result = NULL;
			this->find_loop_node(this->head);
			cout << "\n Loop Node is : " << this->result->data << "\n";
		}
		else
		{
			cout << "\n Loop not exist\n";
		}
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	//Create linked list
	obj.insert(7);
	obj.insert(6);
	obj.insert(2);
	obj.insert(5);
	obj.insert(9);
	obj.insert(4);
	obj.insert(8);
	obj.insert(3);
	//Display all node
	obj.display();
	//Create loop
	obj.head->next->next->next->next->next->next->next->next = obj.head->next->next;
	//Test Case
	obj.loop_node();
	return 0;
}

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
//Include namespace system
using System;

//C# Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node result;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.result = null;
	}
	//insert element
	public void insert(int data)
	{
		//Create  node
		Node node = new Node(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			Node temp = this.head;
			//find last node
			while (temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = node;
		}
	}
	//Display linked list nodes
	public void display()
	{
		if (this.head != null)
		{
			Console.Write(" Linked List :");
			Node temp = this.head;
			while (temp != null)
			{
				Console.Write(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					return;
				}
			}
		}
		else
		{
			Console.WriteLine("Empty Linked List");
		}
	}
	//Find loop node in given linked list
	public Node find_loop_node(Node temp)
	{
		if (temp == null || temp.next == null)
		{
			return temp;
		}
		else if (temp.next.next == null)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			this.result = temp;
			return temp;
		}
		//Get current node
		Node current_node = temp.next;
		//important to control recursion
		temp.next = null;
		temp.next = find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	public void loop_node()
	{
		if (this.head == null)
		{
			Console.Write("Empty Linked List\n");
			return;
		}
		Boolean status = false;
		//Variable which is used to detect loop in linked list
		Node first = this.head;
		Node second = this.head;
		//Check that loop exists in given linked list or not
		while (second != null && second.next != null && second.next.next != null && status == false)
		{
			first = first.next;
			second = second.next.next;
			if (first == second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			this.result = null;
			find_loop_node(this.head);
			Console.Write("\n Loop Node is : " + result.data + "\n");
		}
		else
		{
			Console.Write("\n Loop not exist\n");
		}
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(7);
		obj.insert(6);
		obj.insert(2);
		obj.insert(5);
		obj.insert(9);
		obj.insert(4);
		obj.insert(8);
		obj.insert(3);
		//Display all node
		obj.display();
		//Create loop
		obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;
		//Test Case
		obj.loop_node();
	}
}

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
<?php
//Php Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		//set node value
		$this->data = $data;
		$this->next = null;
	}
}
class MyLinkedList
{
	public $head;
	public $result;
	//Class constructors
	function __construct()
	{
		$this->head = null;
		$this->result = null;
	}
	//insert element
	public	function insert($data)
	{
		//Create  node
		$node = new Node($data);
		if ($this->head == null)
		{
			$this->head = $node;
		}
		else
		{
			$temp = $this->head;
			//find last node
			while ($temp->next != null)
			{
				$temp = $temp->next;
			}
			$temp->next = $node;
		}
	}
	//Display linked list nodes
	public	function display()
	{
		if ($this->head != null)
		{
			echo " Linked List :";
			$temp = $this->head;
			while ($temp != null)
			{
				echo " ". $temp->data;
				$temp = $temp->next;
				if ($temp == $this->head)
				{
					return;
				}
			}
		}
		else
		{
			echo "Empty Linked List";
		}
	}
	//Find loop node in given linked list
	public	function find_loop_node($temp)
	{
		if ($temp == null || $temp->next == null)
		{
			return $temp;
		}
		else if ($temp->next->next == null)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			$this->result = $temp;
			return $temp;
		}
		//Get current node
		$current_node = $temp->next;
		//important to control recursion
		$temp->next = null;
		$temp->next = $this->find_loop_node($current_node);
		return $temp;
	}
	// Handles the request of detect and find loop node in linked list
	public	function loop_node()
	{
		if ($this->head == null)
		{
			echo "Empty Linked List\n";
			return;
		}
		$status = false;
		//Variable which is used to detect loop in linked list
		$first = $this->head;
		$second = $this->head;
		//Check that loop exists in given linked list or not
		while ($second != null && $second->next != null && $second->next->next != null && $status == false)
		{
			$first = $first->next;
			$second = $second->next->next;
			if ($first == $second)
			{
				//loop is found
				$status = true;
			}
		}
		if ($status == true)
		{
			//When loop is exists in linked list
			$this->result = null;
			$this->find_loop_node($this->head);
			echo "\n Loop Node is : ". $this->result->data ."\n";
		}
		else
		{
			echo "\n Loop not exist\n";
		}
	}
}

function main()
{
	$obj = new MyLinkedList();
	//Create linked list
	$obj->insert(7);
	$obj->insert(6);
	$obj->insert(2);
	$obj->insert(5);
	$obj->insert(9);
	$obj->insert(4);
	$obj->insert(8);
	$obj->insert(3);
	//Display all node
	$obj->display();
	//Create loop
	$obj->head->next->next->next->next->next->next->next->next = $obj->head->next->next;
	//Test Case
	$obj->loop_node();
}
main();

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
//Node Js Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node
{
	constructor(data)
	{
		//set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructors
	constructor()
	{
		this.head = null;
		this.result = null;
	}
	//insert element
	insert(data)
	{
		//Create  node
		var node = new Node(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			var temp = this.head;
			//find last node
			while (temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = node;
		}
	}
	//Display linked list nodes
	display()
	{
		if (this.head != null)
		{
			process.stdout.write(" Linked List :");
			var temp = this.head;
			while (temp != null)
			{
				process.stdout.write(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					return;
				}
			}
		}
		else
		{
			process.stdout.write("Empty Linked List");
		}
	}
	//Find loop node in given linked list
	find_loop_node(temp)
	{
		if (temp == null || temp.next == null)
		{
			return temp;
		}
		else if (temp.next.next == null)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			this.result = temp;
			return temp;
		}
		//Get current node
		var current_node = temp.next;
		//important to control recursion
		temp.next = null;
		temp.next = this.find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	loop_node()
	{
		if (this.head == null)
		{
			process.stdout.write("Empty Linked List\n");
			return;
		}
		var status = false;
		//Variable which is used to detect loop in linked list
		var first = this.head;
		var second = this.head;
		//Check that loop exists in given linked list or not
		while (second != null && second.next != null && second.next.next != null && status == false)
		{
			first = first.next;
			second = second.next.next;
			if (first == second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			this.result = null;
			this.find_loop_node(this.head);
			process.stdout.write("\n Loop Node is : " + this.result.data + "\n");
		}
		else
		{
			process.stdout.write("\n Loop not exist\n");
		}
	}
}

function main()
{
	var obj = new MyLinkedList();
	//Create linked list
	obj.insert(7);
	obj.insert(6);
	obj.insert(2);
	obj.insert(5);
	obj.insert(9);
	obj.insert(4);
	obj.insert(8);
	obj.insert(3);
	//Display all node
	obj.display();
	//Create loop
	obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;
	//Test Case
	obj.loop_node();
}
main();

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
# Python 3 Program
# Find modular node in a linked list (from end of linked list)

# Node of LinkedList
class Node :
	
	def __init__(self, data) :
		# set node value
		self.data = data
		self.next = None
	

class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.result = None
	
	# insert element
	def insert(self, data) :
		# Create  node
		node = Node(data)
		if (self.head == None) :
			self.head = node
		else :
			temp = self.head
			# find last node
			while (temp.next != None) :
				temp = temp.next
			
			temp.next = node
		
	
	# Display linked list nodes
	def display(self) :
		if (self.head != None) :
			print(" Linked List :", end = "")
			temp = self.head
			while (temp != None) :
				print(" ", temp.data, end = "")
				temp = temp.next
				if (temp == self.head) :
					return
				
			
		else :
			print("Empty Linked List", end = "")
		
	
	# Find loop node in given linked list
	def find_loop_node(self, temp) :
		if (temp == None or temp.next == None) :
			return temp
		
		elif(temp.next.next == None) :
			#  When get node in loop
			#  In case loop are not exist then result is null
			self.result = temp
			return temp
		
		# Get current node
		current_node = temp.next
		# important to control recursion
		temp.next = None
		temp.next = self.find_loop_node(current_node)
		return temp
	
	#  Handles the request of detect and find loop node in linked list
	def loop_node(self) :
		if (self.head == None) :
			print("Empty Linked List\n", end = "")
			return
		
		status = False
		# Variable which is used to detect loop in linked list
		first = self.head
		second = self.head
		# Check that loop exists in given linked list or not
		while (second != None and second.next != None and second.next.next != None and status == False) :
			first = first.next
			second = second.next.next
			if (first == second) :
				# loop is found
				status = True
			
		
		if (status == True) :
			# When loop is exists in linked list
			self.result = None
			self.find_loop_node(self.head)
			print("\n Loop Node is : ", self.result.data ,"\n", end = "")
		else :
			print("\n Loop not exist\n", end = "")
		
	

def main() :
	obj = MyLinkedList()
	# Create linked list
	obj.insert(7)
	obj.insert(6)
	obj.insert(2)
	obj.insert(5)
	obj.insert(9)
	obj.insert(4)
	obj.insert(8)
	obj.insert(3)
	# Display all node
	obj.display()
	# Create loop
	obj.head.next.next.next.next.next.next.next.next = obj.head.next.next
	# Test Case
	obj.loop_node()

if __name__ == "__main__": main()

Output

 Linked List :  7  6  2  5  9  4  8  3
 Loop Node is :  3
# Ruby Program
# Find modular node in a linked list (from end of linked list)

# Node of LinkedList
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next

	def initialize(data)
		# set node value
		self.data = data
		self.next = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :result
	attr_accessor :head, :result

	# Class constructors
	def initialize()
	
		self.head = nil
		self.result = nil
	end
	# insert element
	def insert(data)
	
		# Create  node
		node = Node.new(data)
		if (self.head == nil)
		
			self.head = node
		else
		
			temp = self.head
			# find last node
			while (temp.next != nil)
			
				temp = temp.next
			end
			temp.next = node
		end
	end
	# Display linked list nodes
	def display()
	
		if (self.head != nil)
		
			print(" Linked List :")
			temp = self.head
			while (temp != nil)
			
				print(" ", temp.data)
				temp = temp.next
				if (temp == self.head)
				
					return
				end
			end
		else
		
			print("Empty Linked List")
		end
	end
	# Find loop node in given linked list
	def find_loop_node(temp)
	
		if (temp == nil || temp.next == nil)
		
			return temp
		elsif(temp.next.next == nil)
		
			#  When get node in loop
			#  In case loop are not exist then result is null
			self.result = temp
			return temp
		end
		# Get current node
		current_node = temp.next
		# important to control recursion
		temp.next = nil
		temp.next = self.find_loop_node(current_node)
		return temp
	end
	#  Handles the request of detect and find loop node in linked list
	def loop_node()
	
		if (self.head == nil)
		
			print("Empty Linked List\n")
			return
		end
		status = false
		# Variable which is used to detect loop in linked list
		first = self.head
		second = self.head
		# Check that loop exists in given linked list or not
		while (second != nil && second.next != nil && second.next.next != nil && status == false)
		
			first = first.next
			second = second.next.next
			if (first == second)
			
				# loop is found
				status = true
			end
		end
		if (status == true)
		
			# When loop is exists in linked list
			self.result = nil
			self.find_loop_node(self.head)
			print("\n Loop Node is : ", @result.data ,"\n")
		else
		
			print("\n Loop not exist\n")
		end
	end
end
def main()

	obj = MyLinkedList.new()
	# Create linked list
	obj.insert(7)
	obj.insert(6)
	obj.insert(2)
	obj.insert(5)
	obj.insert(9)
	obj.insert(4)
	obj.insert(8)
	obj.insert(3)
	# Display all node
	obj.display()
	# Create loop
	obj.head.next.next.next.next.next.next.next.next = obj.head.next.next
	# Test Case
	obj.loop_node()
end
main()

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
//Scala Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node(var data: Int,
	var next: Node)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class MyLinkedList(var head: Node,
	var result: Node)
{
	//Class constructors
	def this()
	{
		this(null, null);
	}
	//insert element
	def insert(data: Int): Unit = {
		//Create  node
		var node: Node = new Node(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			var temp: Node = this.head;
			//find last node
			while (temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = node;
		}
	}
	//Display linked list nodes
	def display(): Unit = {
		if (this.head != null)
		{
			print(" Linked List :");
			var temp: Node = this.head;
			while (temp != null)
			{
				print(" " + temp.data);
				temp = temp.next;
				if (temp == this.head)
				{
					return;
				}
			}
		}
		else
		{
			print("Empty Linked List");
		}
	}
	//Find loop node in given linked list
	def find_loop_node(temp: Node): Node = {
		if (temp == null || temp.next == null)
		{
			return temp;
		}
		else if (temp.next.next == null)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			this.result = temp;
			return temp;
		}
		//Get current node
		var current_node: Node = temp.next;
		//important to control recursion
		temp.next = null;
		temp.next = find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	def loop_node(): Unit = {
		if (this.head == null)
		{
			print("Empty Linked List\n");
			return;
		}
		var status: Boolean = false;
		//Variable which is used to detect loop in linked list
		var first: Node = this.head;
		var second: Node = this.head;
		//Check that loop exists in given linked list or not
		while (second != null && second.next != null && second.next.next != null && status == false)
		{
			first = first.next;
			second = second.next.next;
			if (first == second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			this.result = null;
			find_loop_node(this.head);
			print("\n Loop Node is : " + result.data + "\n");
		}
		else
		{
			print("\n Loop not exist\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		//Create linked list
		obj.insert(7);
		obj.insert(6);
		obj.insert(2);
		obj.insert(5);
		obj.insert(9);
		obj.insert(4);
		obj.insert(8);
		obj.insert(3);
		//Display all node
		obj.display();
		//Create loop
		obj.head.next.next.next.next.next.next.next.next = obj.head.next.next;
		//Test Case
		obj.loop_node();
	}
}

Output

 Linked List : 7 6 2 5 9 4 8 3
 Loop Node is : 3
//Swift Program
//Find modular node in a linked list (from end of linked list)

//Node of LinkedList
class Node
{
	var data: Int;
	var next: Node? ;
	init(_ data: Int)
	{
		//set node value
		self.data = data;
		self.next = nil;
	}
}
class MyLinkedList
{
	var head: Node? ;
	var result: Node? ;
	//Class constructors
	init()
	{
		self.head = nil;
		self.result = nil;
	}
	//insert element
	func insert(_ data: Int)
	{
		//Create  node
		let node: Node? = Node(data);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			var temp: Node? = self.head;
			//find last node
			while (temp!.next != nil)
			{
				temp = temp!.next;
			}
			temp!.next = node;
		}
	}
	//Display linked list nodes
	func display()
	{
		if (self.head != nil)
		{
			print(" Linked List :", terminator: "");
			var temp: Node? = self.head;
			while (temp != nil)
			{
				print(" ", temp!.data, terminator: "");
				temp = temp!.next;
				if (temp === self.head)
				{
					return;
				}
			}
		}
		else
		{
			print("Empty Linked List", terminator: "");
		}
	}
	//Find loop node in given linked list
	func find_loop_node(_ temp: Node? ) -> Node?
	{
		if (temp == nil || temp!.next == nil)
		{
			return temp;
		}
		else if (temp!.next!.next == nil)
		{
			// When get node in loop
			// In case loop are not exist then result is null
			self.result = temp;
			return temp;
		}
		//Get current node
		let current_node: Node? = temp!.next;
		//important to control recursion
		temp!.next = nil;temp!.next = self.find_loop_node(current_node);
		return temp;
	}
	// Handles the request of detect and find loop node in linked list
	func loop_node()
	{
		if (self.head == nil)
		{
			print("Empty Linked List\n", terminator: "");
			return;
		}
		var status: Bool = false;
		//Variable which is used to detect loop in linked list
		var first: Node? = self.head;
		var second: Node? = self.head;
		//Check that loop exists in given linked list or not
		while (second != nil && second!.next != nil && second!.next!.next != nil && status == false)
		{
			first = first!.next;
			second = second!.next!.next;
			if (first === second)
			{
				//loop is found
				status = true;
			}
		}
		if (status == true)
		{
			//When loop is exists in linked list
			self.result = nil;
			let _ = self.find_loop_node(self.head);
			print("\n Loop Node is : ", self.result!.data ,"\n", terminator: "");
		}
		else
		{
			print("\n Loop not exist\n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	//Create linked list
	obj.insert(7);
	obj.insert(6);
	obj.insert(2);
	obj.insert(5);
	obj.insert(9);
	obj.insert(4);
	obj.insert(8);
	obj.insert(3);
	//Display all node
	obj.display();
	//Create loop
	obj.head!.next!.next!.next!.next!.next!.next!.next!.next = obj.head!.next!.next;
	//Test Case
	obj.loop_node();
}
main();

Output

 Linked List :  7  6  2  5  9  4  8  3
 Loop Node is :  3


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







© 2021, kalkicode.com, All rights reserved