# 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>

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;
}
void insert(struct Node **head, int data)
{
struct Node *node = create_node(data);
{
}
else
{
//Find last node
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = node;
}
}
{
{
return;
}
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
{
//Define some auxiliary variables
struct Node *inner = NULL;
struct Node *result = NULL;
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()
{
struct Node *list1 = NULL;
struct Node *list2 = NULL;
struct Node *list3 = NULL;
struct Node *list4 = NULL;
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);
insert( &list2, 6);
insert( &list2, 2);
insert( &list2, 3);
insert( &list2, 3);
insert( &list2, 2);
insert( &list2, 5);
insert( &list2, 3);
first_duplicate(list2);
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

class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructor
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
return;
}
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()
{
this.display();
//Define some auxiliary variables
Node inner = null;
Node result = null;
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)
{
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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
class Node
{
public: int data;
Node *next;
Node(int data)
{
//Set node value
this->data = data;
this->next = NULL;
}
};
{
Node *tail;
//Class constructor
{
this->tail = NULL;
}
//insert node at last of linke list
void insert(int data)
{
//Create a node
Node *node = new Node(data);
{
this->tail = node;
}
else
{
this->tail->next = node;
this->tail = node;
}
}
void display()
{
{
return;
}
cout << "\n Linked List : ";
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()
{
this->display();
//Define some auxiliary variables
Node *inner = NULL;
Node *result = NULL;
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()
{
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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

public class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructor
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
return;
}
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()
{
this.display();
//Define some auxiliary variables
Node inner = null;
Node result = null;
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)
{
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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

class Node
{
public \$data;
public \$next;

function __construct(\$data)
{
//Set node value
\$this->data = \$data;
\$this->next = null;
}
}
{
public \$tail;
//Class constructor
function __construct()
{
\$this->tail = null;
}
//insert node at last of linke list
public	function insert(\$data)
{
//Create a node
\$node = new Node(\$data);
{
\$this->tail = \$node;
}
else
{
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public	function display()
{
{
return;
}
echo "\n Linked List : ";
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()
{
\$this->display();
//Define some auxiliary variables
\$inner = null;
\$result = null;
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->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();
\$list2->insert(6);
\$list2->insert(2);
\$list2->insert(3);
\$list2->insert(3);
\$list2->insert(2);
\$list2->insert(5);
\$list2->insert(3);
\$list2->first_duplicate();
\$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

class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.next = null;
}
}
{
//Class constructor
constructor()
{
this.tail = null;
}
//insert node at last of linke list
insert(data)
{
//Create a node
var node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
display()
{
{
return;
}
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()
{
this.display();
//Define some auxiliary variables
var inner = null;
var result = null;
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()
{
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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

class Node :

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

# Class constructor
def __init__(self) :
self.tail = None

# insert node at last of linke list
def insert(self, data) :
# Create a node
node = Node(data)
self.tail = node
else :
self.tail.next = node
self.tail = node

def display(self) :
return

print("\n Linked List : ", end = "")
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) :
self.display()
# Define some auxiliary variables
inner = None
result = None
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.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()
list2.insert(6)
list2.insert(2)
list2.insert(3)
list2.insert(3)
list2.insert(2)
list2.insert(5)
list2.insert(3)
list2.first_duplicate()
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

class Node

# Define the accessor and reader of class Node
attr_accessor :data, :next
def initialize(data)

# Set node value
self.data = data
self.next = nil
end
end

# Class constructor
def initialize()

self.tail = nil
end
# insert node at last of linke list
def insert(data)

# Create a node
node = Node.new(data)

self.tail = node
else

self.tail.next = node
self.tail = node
end
end
def display()

return
end
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()

self.display()
# Define some auxiliary variables
inner = nil
result = nil
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.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()
list2.insert(6)
list2.insert(2)
list2.insert(3)
list2.insert(3)
list2.insert(2)
list2.insert(5)
list2.insert(3)
list2.first_duplicate()
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

class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
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);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
def display(): Unit = {
{
return;
}
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 = {
this.display();
//Define some auxiliary variables
var inner: Node = null;
var result: Node = null;
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 = {
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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

class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.next = nil;
}
}
{
var tail: Node? ;
//Class constructor
init()
{
self.tail = nil;
}
//insert node at last of linke list
func insert(_ data: Int)
{
//Create a node
let node: Node? = Node(data);
{
self.tail = node;
}
else
{
self.tail!.next = node;
self.tail = node;
}
}
func display()
{
{
return;
}
print("\n Linked List : ", terminator: "");
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()
{
self.display();
//Define some auxiliary variables
var inner: Node? = nil;
var result: Node? = nil;
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()
{
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();
list2.insert(6);
list2.insert(2);
list2.insert(3);
list2.insert(3);
list2.insert(2);
list2.insert(5);
list2.insert(3);
list2.first_duplicate();
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.