Find the first duplicate element in the linked list

Here given code implementation process.

// C Program
// Find the first duplicate element in the linked list
#include <stdio.h>
 //For malloc function
#include <stdlib.h>

//Linked List Node
struct Node
{
    int data;
    struct Node *next;
};
//Create a node of linked list
struct Node *create_node(int data)
{
    //Create dynamic node
    struct Node *node = (struct Node *) malloc(sizeof(struct Node));
    if (node == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        //Set initial node value
        node->data = data;
        node->next = NULL;
    }
    return node;
}
//Add new node at end of linked list 
void insert(struct Node **head, int data)
{
    struct Node *node = create_node(data);
    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("\nEmpty linked list\n");
        return;
    }
    struct Node *temp = head;
    printf("\n Linked List : ");
    //iterating linked list elements
    while (temp != NULL)
    {
        printf("  %d", temp->data);
        //visit to next node
        temp = temp->next;
    }
}
//Find first repeating element from front to end in a linked list
//Solution are takes O(n*n) time
void first_duplicate(struct Node *head)
{
    //display linked list elements
    display(head);
    //Define some auxiliary variables
    struct Node *outer = head;
    struct Node *inner = NULL;
    struct Node *result = NULL;
    //iterating linked list elements
    while (outer != NULL && result == NULL)
    {
        //get next node
        inner = outer->next;
        //iterating linked list elements from current node to end
        while (inner != NULL && result == NULL)
        {
            if (inner->data == outer->data)
            {
                //When get first duplicate node exist
                result = outer;
            }
            inner = inner->next;
        }
        //visit to next node
        outer = outer->next;
    }
    if (result == NULL)
    {
        printf("\n First duplicate : None");
    }
    else
    {
        printf("\n First duplicate : %d", result->data);
    }
    //
}
int main()
{
    //Define few empty  linked list
    struct Node *list1 = NULL;
    struct Node *list2 = NULL;
    struct Node *list3 = NULL;
    struct Node *list4 = NULL;
    //Add node in first linked list
    insert( &list1, 6);
    insert( &list1, 4);
    insert( &list1, 5);
    insert( &list1, 9);
    insert( &list1, 3);
    insert( &list1, 5);
    insert( &list1, 4);
    insert( &list1, 9);;
    first_duplicate(list1);
    //Add node in second linked list
    insert( &list2, 6);
    insert( &list2, 2);
    insert( &list2, 3);
    insert( &list2, 3);
    insert( &list2, 2);
    insert( &list2, 5);
    insert( &list2, 3);
    first_duplicate(list2);
    //Add node in third linked list
    insert( &list3, 2);
    insert( &list3, 1);
    insert( &list3, 8);
    insert( &list3, 4);
    first_duplicate(list3);
    return 0;
}

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
// Java Program
// Find the first duplicate element in the 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;
    }
}
public class MyLinkedList
{
    public Node head;
    public Node tail;
    //Class constructor
    public MyLinkedList()
    {
        this.head = null;
        this.tail = null;
    }
    //insert node at last of linke list
    public void insert(int data)
    {
        //Create a node
        Node node = new Node(data);
        if (this.head == null)
        {
            //When linked list empty add first node
            this.head = node;
            this.tail = node;
        }
        else
        {
            //Add new node at end of linked list
            this.tail.next = node;
            this.tail = node;
        }
    }
    //Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            System.out.print("\nEmpty linked list\n");
            return;
        }
        Node temp = this.head;
        System.out.print("\n Linked List : ");
        //iterating linked list elements
        while (temp != null)
        {
            //display node value
            System.out.print("  " + temp.data);
            //visit to next node
            temp = temp.next;
        }
    }
    //Find first repeating element from front to end in a linked list
    //Solution are takes O(n*n) time
    public void first_duplicate()
    {
        //display linked list elements
        this.display();
        //Define some auxiliary variables
        Node outer = this.head;
        Node inner = null;
        Node result = null;
        //iterating linked list elements
        while (outer != null && result == null)
        {
            //get next node
            inner = outer.next;
            //iterating linked list elements from current node to end
            while (inner != null && result == null)
            {
                if (inner.data == outer.data)
                {
                    //When get first duplicate node exist
                    result = outer;
                }
                inner = inner.next;
            }
            //visit to next node
            outer = outer.next;
        }
        if (result == null)
        {
            System.out.print("\n First duplicate : None");
        }
        else
        {
            System.out.print("\n First duplicate : " + result.data);
        }
    }
    public static void main(String[] args)
    {
        MyLinkedList list1 = new MyLinkedList();
        MyLinkedList list2 = new MyLinkedList();
        MyLinkedList list3 = new MyLinkedList();
        //Add node in first linked list
        list1.insert(6);
        list1.insert(4);
        list1.insert(5);
        list1.insert(9);
        list1.insert(3);
        list1.insert(5);
        list1.insert(4);
        list1.insert(9);;
        list1.first_duplicate();
        //Add node in second linked list
        list2.insert(6);
        list2.insert(2);
        list2.insert(3);
        list2.insert(3);
        list2.insert(2);
        list2.insert(5);
        list2.insert(3);
        list2.first_duplicate();
        //Add node in third linked list
        list3.insert(2);
        list3.insert(1);
        list3.insert(8);
        list3.insert(4);
        list3.first_duplicate();
    }
}

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find the first duplicate element in the 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 *tail;
    //Class constructor
    MyLinkedList()
    {
        this->head = NULL;
        this->tail = NULL;
    }
    //insert node at last of linke list
    void insert(int data)
    {
        //Create a node
        Node *node = new Node(data);
        if (this->head == NULL)
        {
            //When linked list empty add first node
            this->head = node;
            this->tail = node;
        }
        else
        {
            //Add new node at end of linked list
            this->tail->next = node;
            this->tail = node;
        }
    }
    //Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            cout << "\nEmpty linked list\n";
            return;
        }
        Node *temp = this->head;
        cout << "\n Linked List : ";
        //iterating linked list elements
        while (temp != NULL)
        {
            //display node value
            cout << "  " << temp->data;
            //visit to next node
            temp = temp->next;
        }
    }

    //Find first repeating element from front to end in a linked list
    //Solution are takes O(n*n) time
    void first_duplicate()
    {
        //display linked list elements
        this->display();
        //Define some auxiliary variables
        Node *outer = this->head;
        Node *inner = NULL;
        Node *result = NULL;
        //iterating linked list elements
        while (outer != NULL && result == NULL)
        {
            //get next node
            inner = outer->next;
            //iterating linked list elements from current node to end
            while (inner != NULL && result == NULL)
            {
                if (inner->data == outer->data)
                {
                    //When get first duplicate node exist
                    result = outer;
                }
                inner = inner->next;
            }
            //visit to next node
            outer = outer->next;
        }
        if (result == NULL)
        {
            cout << "\n First duplicate : None";
        }
        else
        {
            cout << "\n First duplicate : " << result->data;
        }
    }
};
int main()
{
    MyLinkedList list1 = MyLinkedList();
    MyLinkedList list2 = MyLinkedList();
    MyLinkedList list3 = MyLinkedList();
    //Add node in first linked list
    list1.insert(6);
    list1.insert(4);
    list1.insert(5);
    list1.insert(9);
    list1.insert(3);
    list1.insert(5);
    list1.insert(4);
    list1.insert(9);;
    list1.first_duplicate();
    //Add node in second linked list
    list2.insert(6);
    list2.insert(2);
    list2.insert(3);
    list2.insert(3);
    list2.insert(2);
    list2.insert(5);
    list2.insert(3);
    list2.first_duplicate();
    //Add node in third linked list
    list3.insert(2);
    list3.insert(1);
    list3.insert(8);
    list3.insert(4);
    list3.first_duplicate();
    return 0;
}

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
//Include namespace system
using System;
// C# Program
// Find the first duplicate element in the linked list

//Node of LinkedList
public class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
public class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructor
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int data)
	{
		//Create a node
		Node node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			Console.Write("\nEmpty linked list\n");
			return;
		}
		Node temp = this.head;
		Console.Write("\n Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			//display node value
			Console.Write("  " + temp.data);
			//visit to next node
			temp = temp.next;
		}
	}
	//Find first repeating element from front to end in a linked list
	//Solution are takes O(n*n) time
	public void first_duplicate()
	{
		//display linked list elements
		this.display();
		//Define some auxiliary variables
		Node outer = this.head;
		Node inner = null;
		Node result = null;
		//iterating linked list elements
		while (outer != null && result == null)
		{
			//get next node
			inner = outer.next;
			//iterating linked list elements from current node to end
			while (inner != null && result == null)
			{
				if (inner.data == outer.data)
				{
					//When get first duplicate node exist
					result = outer;
				}
				inner = inner.next;
			}
			//visit to next node
			outer = outer.next;
		}
		if (result == null)
		{
			Console.Write("\n First duplicate : None");
		}
		else
		{
			Console.Write("\n First duplicate : " + result.data);
		}
	}
	public static void Main(String[] args)
	{
		MyLinkedList list1 = new MyLinkedList();
		MyLinkedList list2 = new MyLinkedList();
		MyLinkedList list3 = new MyLinkedList();
		//Add node in first linked list
		list1.insert(6);
		list1.insert(4);
		list1.insert(5);
		list1.insert(9);
		list1.insert(3);
		list1.insert(5);
		list1.insert(4);
		list1.insert(9);;
		list1.first_duplicate();
		//Add node in second linked list
		list2.insert(6);
		list2.insert(2);
		list2.insert(3);
		list2.insert(3);
		list2.insert(2);
		list2.insert(5);
		list2.insert(3);
		list2.first_duplicate();
		//Add node in third linked list
		list3.insert(2);
		list3.insert(1);
		list3.insert(8);
		list3.insert(4);
		list3.first_duplicate();
	}
}

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
<?php
// Php Program
// Find the first duplicate element in the 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 $tail;
	//Class constructor
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//insert node at last of linke list
	public	function insert($data)
	{
		//Create a node
		$node = new Node($data);
		if ($this->head == null)
		{
			//When linked list empty add first node
			$this->head = $node;
			$this->tail = $node;
		}
		else
		{
			//Add new node at end of linked list
			$this->tail->next = $node;
			$this->tail = $node;
		}
	}
	//Display linked list element
	public	function display()
	{
		if ($this->head == null)
		{
			echo "\nEmpty linked list\n";
			return;
		}
		$temp = $this->head;
		echo "\n Linked List : ";
		//iterating linked list elements
		while ($temp != null)
		{
			//display node value
			echo "  ". $temp->data;
			//visit to next node
			$temp = $temp->next;
		}
	}
	//Find first repeating element from front to end in a linked list
	//Solution are takes O(n*n) time
	public	function first_duplicate()
	{
		//display linked list elements
		$this->display();
		//Define some auxiliary variables
		$outer = $this->head;
		$inner = null;
		$result = null;
		//iterating linked list elements
		while ($outer != null && $result == null)
		{
			//get next node
			$inner = $outer->next;
			//iterating linked list elements from current node to end
			while ($inner != null && $result == null)
			{
				if ($inner->data == $outer->data)
				{
					//When get first duplicate node exist
					$result = $outer;
				}
				$inner = $inner->next;
			}
			//visit to next node
			$outer = $outer->next;
		}
		if ($result == null)
		{
			echo "\n First duplicate : None";
		}
		else
		{
			echo "\n First duplicate : ". $result->data;
		}
	}
}

function main()
{
	$list1 = new MyLinkedList();
	$list2 = new MyLinkedList();
	$list3 = new MyLinkedList();
	//Add node in first linked list
	$list1->insert(6);
	$list1->insert(4);
	$list1->insert(5);
	$list1->insert(9);
	$list1->insert(3);
	$list1->insert(5);
	$list1->insert(4);
	$list1->insert(9);;
	$list1->first_duplicate();
	//Add node in second linked list
	$list2->insert(6);
	$list2->insert(2);
	$list2->insert(3);
	$list2->insert(3);
	$list2->insert(2);
	$list2->insert(5);
	$list2->insert(3);
	$list2->first_duplicate();
	//Add node in third linked list
	$list3->insert(2);
	$list3->insert(1);
	$list3->insert(8);
	$list3->insert(4);
	$list3->first_duplicate();
}
main();

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
// Node Js Program
// Find the first duplicate element in the linked list

//Node of LinkedList
class Node
{
	constructor(data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructor
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	insert(data)
	{
		//Create a node
		var node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	display()
	{
		if (this.head == null)
		{
			process.stdout.write("\nEmpty linked list\n");
			return;
		}
		var temp = this.head;
		process.stdout.write("\n Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			//display node value
			process.stdout.write("  " + temp.data);
			//visit to next node
			temp = temp.next;
		}
	}
	//Find first repeating element from front to end in a linked list
	//Solution are takes O(n*n) time
	first_duplicate()
	{
		//display linked list elements
		this.display();
		//Define some auxiliary variables
		var outer = this.head;
		var inner = null;
		var result = null;
		//iterating linked list elements
		while (outer != null && result == null)
		{
			//get next node
			inner = outer.next;
			//iterating linked list elements from current node to end
			while (inner != null && result == null)
			{
				if (inner.data == outer.data)
				{
					//When get first duplicate node exist
					result = outer;
				}
				inner = inner.next;
			}
			//visit to next node
			outer = outer.next;
		}
		if (result == null)
		{
			process.stdout.write("\n First duplicate : None");
		}
		else
		{
			process.stdout.write("\n First duplicate : " + result.data);
		}
	}
}

function main()
{
	var list1 = new MyLinkedList();
	var list2 = new MyLinkedList();
	var list3 = new MyLinkedList();
	//Add node in first linked list
	list1.insert(6);
	list1.insert(4);
	list1.insert(5);
	list1.insert(9);
	list1.insert(3);
	list1.insert(5);
	list1.insert(4);
	list1.insert(9);;
	list1.first_duplicate();
	//Add node in second linked list
	list2.insert(6);
	list2.insert(2);
	list2.insert(3);
	list2.insert(3);
	list2.insert(2);
	list2.insert(5);
	list2.insert(3);
	list2.first_duplicate();
	//Add node in third linked list
	list3.insert(2);
	list3.insert(1);
	list3.insert(8);
	list3.insert(4);
	list3.first_duplicate();
}
main();

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
#  Python 3 Program
#  Find the first duplicate element in the linked list

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

class MyLinkedList :
	
	# Class constructor
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def insert(self, data) :
		# Create a node
		node = Node(data)
		if (self.head == None) :
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else :
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		
	
	# Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\nEmpty linked list")
			return
		
		temp = self.head
		print("\n Linked List : ", end = "")
		# iterating linked list elements
		while (temp != None) :
			# display node value
			print("  ", temp.data, end = "")
			# visit to next node
			temp = temp.next
		
	
	# Find first repeating element from front to end in a linked list
	# Solution are takes O(n*n) time
	def first_duplicate(self) :
		# display linked list elements
		self.display()
		# Define some auxiliary variables
		outer = self.head
		inner = None
		result = None
		# iterating linked list elements
		while (outer != None and result == None) :
			# get next node
			inner = outer.next
			# iterating linked list elements from current node to end
			while (inner != None and result == None) :
				if (inner.data == outer.data) :
					# When get first duplicate node exist
					result = outer
				
				inner = inner.next
			
			# visit to next node
			outer = outer.next
		
		if (result == None) :
			print("\n First duplicate : None", end = "")
		else :
			print("\n First duplicate : ", result.data, end = "")
		
	

def main() :
	list1 = MyLinkedList()
	list2 = MyLinkedList()
	list3 = MyLinkedList()
	# Add node in first linked list
	list1.insert(6)
	list1.insert(4)
	list1.insert(5)
	list1.insert(9)
	list1.insert(3)
	list1.insert(5)
	list1.insert(4)
	list1.insert(9)
	list1.first_duplicate()
	# Add node in second linked list
	list2.insert(6)
	list2.insert(2)
	list2.insert(3)
	list2.insert(3)
	list2.insert(2)
	list2.insert(5)
	list2.insert(3)
	list2.first_duplicate()
	# Add node in third linked list
	list3.insert(2)
	list3.insert(1)
	list3.insert(8)
	list3.insert(4)
	list3.first_duplicate()

if __name__ == "__main__": main()

Output

 Linked List :    6   4   5   9   3   5   4   9
 First duplicate :  4
 Linked List :    6   2   3   3   2   5   3
 First duplicate :  2
 Linked List :    2   1   8   4
 First duplicate : None
#  Ruby Program
#  Find the first duplicate element in the 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, :tail
	attr_accessor :head, :tail

	# Class constructor
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def insert(data)
	
		# Create a node
		node = Node.new(data)
		if (self.head == nil)
		
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else
		
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		end
	end
	# Display linked list element
	def display()
	
		if (self.head == nil)
		
			print("\nEmpty linked list\n")
			return
		end
		temp = self.head
		print("\n Linked List : ")
		# iterating linked list elements
		while (temp != nil)
		
			# display node value
			print("  ", temp.data)
			# visit to next node
			temp = temp.next
		end
	end
	# Find first repeating element from front to end in a linked list
	# Solution are takes O(n*n) time
	def first_duplicate()
	
		# display linked list elements
		self.display()
		# Define some auxiliary variables
		outer = self.head
		inner = nil
		result = nil
		# iterating linked list elements
		while (outer != nil && result == nil)
		
			# get next node
			inner = outer.next
			# iterating linked list elements from current node to end
			while (inner != nil && result == nil)
			
				if (inner.data == outer.data)
				
					# When get first duplicate node exist
					result = outer
				end
				inner = inner.next
			end
			# visit to next node
			outer = outer.next
		end
		if (result == nil)
		
			print("\n First duplicate : None")
		else
		
			print("\n First duplicate : ", result.data)
		end
	end
end
def main()

	list1 = MyLinkedList.new()
	list2 = MyLinkedList.new()
	list3 = MyLinkedList.new()
	# Add node in first linked list
	list1.insert(6)
	list1.insert(4)
	list1.insert(5)
	list1.insert(9)
	list1.insert(3)
	list1.insert(5)
	list1.insert(4)
	list1.insert(9)
	list1.first_duplicate()
	# Add node in second linked list
	list2.insert(6)
	list2.insert(2)
	list2.insert(3)
	list2.insert(3)
	list2.insert(2)
	list2.insert(5)
	list2.insert(3)
	list2.first_duplicate()
	# Add node in third linked list
	list3.insert(2)
	list3.insert(1)
	list3.insert(8)
	list3.insert(4)
	list3.first_duplicate()
end
main()

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
// Scala Program
// Find the first duplicate element in the 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 tail: Node)
{
	//Class constructor
	def this()
	{
		this(null, null);
	}
	//insert node at last of linke list
	def insert(data: Int): Unit = {
		//Create a node
		var node: Node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	def display(): Unit = {
		if (this.head == null)
		{
			print("\nEmpty linked list\n");
			return;
		}
		var temp: Node = this.head;
		print("\n Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			//display node value
			print("  " + temp.data);
			//visit to next node
			temp = temp.next;
		}
	}
	//Find first repeating element from front to end in a linked list
	//Solution are takes O(n*n) time
	def first_duplicate(): Unit = {
		//display linked list elements
		this.display();
		//Define some auxiliary variables
		var outer: Node = this.head;
		var inner: Node = null;
		var result: Node = null;
		//iterating linked list elements
		while (outer != null && result == null)
		{
			//get next node
			inner = outer.next;
			//iterating linked list elements from current node to end
			while (inner != null && result == null)
			{
				if (inner.data == outer.data)
				{
					//When get first duplicate node exist
					result = outer;
				}
				inner = inner.next;
			}
			//visit to next node
			outer = outer.next;
		}
		if (result == null)
		{
			print("\n First duplicate : None");
		}
		else
		{
			print("\n First duplicate : " + result.data);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var list1: MyLinkedList = new MyLinkedList();
		var list2: MyLinkedList = new MyLinkedList();
		var list3: MyLinkedList = new MyLinkedList();
		//Add node in first linked list
		list1.insert(6);
		list1.insert(4);
		list1.insert(5);
		list1.insert(9);
		list1.insert(3);
		list1.insert(5);
		list1.insert(4);
		list1.insert(9);
		list1.first_duplicate();
		//Add node in second linked list
		list2.insert(6);
		list2.insert(2);
		list2.insert(3);
		list2.insert(3);
		list2.insert(2);
		list2.insert(5);
		list2.insert(3);
		list2.first_duplicate();
		//Add node in third linked list
		list3.insert(2);
		list3.insert(1);
		list3.insert(8);
		list3.insert(4);
		list3.first_duplicate();
	}
}

Output

 Linked List :   6  4  5  9  3  5  4  9
 First duplicate : 4
 Linked List :   6  2  3  3  2  5  3
 First duplicate : 2
 Linked List :   2  1  8  4
 First duplicate : None
// Swift Program
// Find the first duplicate element in the 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 tail: Node? ;
	//Class constructor
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	//insert node at last of linke list
	func insert(_ data: Int)
	{
		//Create a node
		let node: Node? = Node(data);
		if (self.head == nil)
		{
			//When linked list empty add first node
			self.head = node;
			self.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			self.tail!.next = node;
			self.tail = node;
		}
	}
	//Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			print("\nEmpty linked list\n", terminator: "");
			return;
		}
		var temp: Node? = self.head;
		print("\n Linked List : ", terminator: "");
		//iterating linked list elements
		while (temp != nil)
		{
			//display node value
			print("  ", temp!.data, terminator: "");
			//visit to next node
			temp = temp!.next;
		}
	}
	//Find first repeating element from front to end in a linked list
	//Solution are takes O(n*n) time
	func first_duplicate()
	{
		//display linked list elements
		self.display();
		//Define some auxiliary variables
		var outer: Node? = self.head;
		var inner: Node? = nil;
		var result: Node? = nil;
		//iterating linked list elements
		while (outer != nil && result == nil)
		{
			//get next node
			inner = outer!.next;
			//iterating linked list elements from current node to end
			while (inner != nil && result == nil)
			{
				if (inner!.data == outer!.data)
				{
					//When get first duplicate node exist
					result = outer;
				}
				inner = inner!.next;
			}
			//visit to next node
			outer = outer!.next;
		}
		if (result == nil)
		{
			print("\n First duplicate : None", terminator: "");
		}
		else
		{
			print("\n First duplicate : ", result!.data, terminator: "");
		}
	}
}
func main()
{
	let list1: MyLinkedList = MyLinkedList();
	let list2: MyLinkedList = MyLinkedList();
	let list3: MyLinkedList = MyLinkedList();
    //Add node in first linked list
    list1.insert(6);
    list1.insert(4);
    list1.insert(5);
    list1.insert(9);
    list1.insert(3);
    list1.insert(5);
    list1.insert(4);
    list1.insert(9);
    list1.first_duplicate();
    //Add node in second linked list
    list2.insert(6);
    list2.insert(2);
    list2.insert(3);
    list2.insert(3);
    list2.insert(2);
    list2.insert(5);
    list2.insert(3);
    list2.first_duplicate();
    //Add node in third linked list
    list3.insert(2);
    list3.insert(1);
    list3.insert(8);
    list3.insert(4);
    list3.first_duplicate();
}
main();

Output

 Linked List :    6   4   5   9   3   5   4   9
 First duplicate :  4
 Linked List :    6   2   3   3   2   5   3
 First duplicate :  2
 Linked List :    2   1   8   4
 First duplicate : None

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