# Find the common nodes in two singly linked list

Given two linked list which consists similar type of node values. Our goal is to print all common node which is present in this linked list.

`````` Example A
---------
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Output :  [3   8   -2   9]

Example B
---------
2 → 11 → 2 → 4 → NULL
4 → 2 → 8 → 6 → -3 → NULL

Output : [2  2  4]``````

That is an problems of linked list traversal, which is concurrent execute two linked list and test similar nodes. Given below solution is based on simple approach. Its take O(n^2) time.

``````// C Program
// Find the common nodes in two singly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->tail = NULL;
}
return sll;
}
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
appendNode(sll, node);
}
void display(struct SingleLL *sll)
{
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Find common nodes
void findCommonNodes(struct SingleLL *sll1, struct SingleLL *sll2)
{
{
return;
}
display(sll1);
display(sll2);
printf("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
int status = 0;
int counter = 0;
while (auxiliary != NULL)
{
// Compare first linked list node to second linked list node value
while (deviation != NULL)
{
if (deviation->data == auxiliary->data)
{
// Print common node
printf("  %d ", auxiliary->data);
// Like a break operation
deviation = NULL;
// Active state because we are got similar node
status = 1;
counter++;
}
else
{
// Visit to next node
deviation = deviation->next;
}
}
// Visit to next node
auxiliary = auxiliary->next;
// Start to first node of second linked list
}
if (status == 0)
{
// When no common node exists
printf(" None \n");
}
else
{
printf("\n Total common element is : %d\n", counter);
}
}
int main()
{
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
findCommonNodes(sll1, sll2);
return 0;
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3   8   -2   9
Total common element is : 4``````
``````/*
Java Program
Find the common nodes in two singly linked list
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}

{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}

public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Find common nodes
public void findCommonNodes(SingleLL second)
{
{
return;
}
this.display();
second.display();
System.out.print("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
boolean status = false;
int counter = 0;
while (auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (deviation != null)
{
if (deviation.data == auxiliary.data)
{
// Print common node
System.out.print("  " + auxiliary.data );
// Like a break operation
deviation = null;
// Active state because we are got similar node
status = true;
// increase resultant count by 1
counter++;
}
else
{
// Visit to next node
deviation = deviation.next;
}
}
// Visit to next node
auxiliary = auxiliary.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
System.out.print(" None \n");
}
else
{
System.out.print("\n Total common element is : " + counter + "\n");
}
}

public static void main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Find the common nodes in two singly linked list
*/
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list\n";
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Find common nodes
void findCommonNodes(SingleLL second)
{
{
return;
}
cout << " Linked List 1 \n";
this->display();
cout << " Linked List 2 \n";
second.display();
cout << "\n Common Value \n";
// Get first node of both linked list
// Define some counter variables
bool status = false;
int counter = 0;
while (auxiliary != NULL)
{
// Compare first linked list node to second linked list node value
while (deviation != NULL)
{
if (deviation->data == auxiliary->data)
{
// increase resultant count by 1
// Print common node
cout << "  " << auxiliary->data;
// Like a break operation
deviation = NULL;
// Active state because we are got similar node
status = true;
counter++;
}
else
{
// Visit to next node
deviation = deviation->next;
}
}
// Visit to next node
auxiliary = auxiliary->next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
cout << " None \n";
}
else
{
cout << "\n Total common element is : " << counter << "\n";
}
}
};
int main()
{
SingleLL sll1 = SingleLL();
SingleLL sll2 = SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
return 0;
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````// Include namespace system
using System;
/*
C# Program
Find the common nodes in two singly linked list
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Find common nodes
public void findCommonNodes(SingleLL second)
{
{
return;
}
this.display();
second.display();
Console.Write("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
Boolean status = false;
int counter = 0;
while (auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (deviation != null)
{
if (deviation.data == auxiliary.data)
{
// increase resultant count by 1
// Print common node
Console.Write("  " + auxiliary.data);
// Like a break operation
deviation = null;
// Active state because we are got similar node
status = true;
counter++;
}
else
{
// Visit to next node
deviation = deviation.next;
}
}
// Visit to next node
auxiliary = auxiliary.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
Console.Write(" None \n");
}
else
{
Console.Write("\n Total common element is : " + counter + "\n");
}
}
public static void Main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````<?php
/*
Php Program
Find the common nodes in two singly linked list
*/
{
public \$data;
public \$next;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
}
}
class SingleLL
{
public \$tail;

function __construct()
{
\$this->tail = null;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
return;
}
while (\$temp != null)
{
echo " ". \$temp->data ." →";
// Visit to next node
\$temp = \$temp->next;
}
echo " NULL\n";
}
// Find common nodes
public	function findCommonNodes(\$second)
{
{
return;
}
echo " Linked List 1 \n";
\$this->display();
echo " Linked List 2 \n";
\$second->display();
echo "\n Common Value \n";
// Get first node of both linked list
// Define some counter variables
\$status = false;
\$counter = 0;
while (\$auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (\$deviation != null)
{
if (\$deviation->data == \$auxiliary->data)
{
// increase resultant count by 1
// Print common node
echo "  ". \$auxiliary->data;
// Like a break operation
\$deviation = null;
// Active state because we are got similar node
\$status = true;
\$counter++;
}
else
{
// Visit to next node
\$deviation = \$deviation->next;
}
}
// Visit to next node
\$auxiliary = \$auxiliary->next;
// Start to first node of second linked list
}
if (\$status == false)
{
// When no common node exists
echo " None \n";
}
else
{
echo "\n Total common element is : ". \$counter ."\n";
}
}
}

function main()
{
\$sll1 = new SingleLL();
\$sll2 = new SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
\$sll1->findCommonNodes(\$sll2);
}
main();``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````/*
Node Js Program
Find the common nodes in two singly linked list
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Find common nodes
findCommonNodes(second)
{
{
return;
}
this.display();
second.display();
process.stdout.write("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
var status = false;
var counter = 0;
while (auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (deviation != null)
{
if (deviation.data == auxiliary.data)
{
// increase resultant count by 1
// Print common node
process.stdout.write("  " + auxiliary.data);
// Like a break operation
deviation = null;
// Active state because we are got similar node
status = true;
counter++;
}
else
{
// Visit to next node
deviation = deviation.next;
}
}
// Visit to next node
auxiliary = auxiliary.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
process.stdout.write(" None \n");
}
else
{
process.stdout.write("\n Total common element is : " + counter + "\n");
}
}
}

function main()
{
var sll1 = new SingleLL();
var sll2 = new SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}
main();``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````#   Python 3 Program
#   Find the common nodes in two singly linked list

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :

def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

#  Find common nodes
def findCommonNodes(self, second) :
return

self.display()
second.display()
print("\n Common Value ")
#  Get first node of both linked list
#  Define some counter variables
status = False
counter = 0
while (auxiliary != None) :
#  Compare first linked list node to second linked list node value
while (deviation != None) :
if (deviation.data == auxiliary.data) :
#  Print common node
print("  ", auxiliary.data, end = "")
#  Like a break operation
deviation = None
#  Active state because we are got similar node
status = True
#  increase resultant count by 1
counter += 1
else :
#  Visit to next node
deviation = deviation.next

#  Visit to next node
auxiliary = auxiliary.next
#  Start to first node of second linked list

if (status == False) :
#  When no common node exists
print(" None ")
else :
print("\n Total common element is : ", counter )

def main() :
sll1 = SingleLL()
sll2 = SingleLL()
#   3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
#   4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2)

if __name__ == "__main__": main()``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3   8   -2   9
Total common element is :  4``````
``````#   Ruby Program
#   Find the common nodes in two singly linked list

attr_accessor :data, :next

def initialize(data)
self.data = data
self.next = nil
end

end

class SingleLL
# Define the accessor and reader of class SingleLL

def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

#  Find common nodes
def findCommonNodes(second)
return
end

self.display()
second.display()
print("\n Common Value \n")
#  Get first node of both linked list
#  Define some counter variables
status = false
counter = 0
while (auxiliary != nil)
#  Compare first linked list node to second linked list node value
while (deviation != nil)
if (deviation.data == auxiliary.data)
#  Print common node
print("  ", auxiliary.data)
#  Like a break operation
deviation = nil
#  Active state because we are got similar node
status = true
#  increase resultant count by 1
counter += 1
else
#  Visit to next node
deviation = deviation.next
end

end

#  Visit to next node
auxiliary = auxiliary.next
#  Start to first node of second linked list
end

if (status == false)
#  When no common node exists
print(" None \n")
else
print("\n Total common element is : ", counter ,"\n")
end

end

end

def main()
sll1 = SingleLL.new()
sll2 = SingleLL.new()
#   3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
#   4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2)
end

main()``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4
``````
``````/*
Scala Program
Find the common nodes in two singly linked list
*/
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null, null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Find common nodes
def findCommonNodes(second: SingleLL): Unit = {
{
return;
}
this.display();
second.display();
print("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
var status: Boolean = false;
var counter: Int = 0;
while (auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (deviation != null)
{
if (deviation.data == auxiliary.data)
{
// increase resultant count by 1
// Print common node
print("  " + auxiliary.data);
// Like a break operation
deviation = null;
// Active state because we are got similar node
status = true;
counter += 1;
}
else
{
// Visit to next node
deviation = deviation.next;
}
}
// Visit to next node
auxiliary = auxiliary.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
print(" None \n");
}
else
{
print("\n Total common element is : " + counter + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll1: SingleLL = new SingleLL();
var sll2: SingleLL = new SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````
``````/*
Swift 4 Program
Find the common nodes in two singly linked list
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Find common nodes
func findCommonNodes(_ second: SingleLL)
{
{
return;
}
self.display();
second.display();
print("\n Common Value ");
// Get first node of both linked list
// Define some counter variables
var status: Bool = false;
var counter: Int = 0;
while (auxiliary  != nil)
{
// Compare first linked list node to second linked list node value
while (deviation  != nil)
{
if (deviation!.data == auxiliary!.data)
{
// increase resultant count by 1
// Print common node
print("  ", auxiliary!.data, terminator: "");
// Like a break operation
deviation = nil;
// Active state because we are got similar node
status = true;
counter += 1;
}
else
{
// Visit to next node
deviation = deviation!.next;
}
}
// Visit to next node
auxiliary = auxiliary!.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
print(" None ");
}
else
{
print("\n Total common element is : ", counter );
}
}
}
func main()
{
let sll1: SingleLL = SingleLL();
let sll2: SingleLL = SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}
main();``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3   8   -2   9
Total common element is :  4``````
``````/*
Kotlin Program
Find the common nodes in two singly linked list
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Find common nodes
fun findCommonNodes(second: SingleLL): Unit
{
{
return;
}
this.display();
second.display();
print("\n Common Value \n");
// Get first node of both linked list
// Define some counter variables
var status: Boolean = false;
var counter: Int = 0;
while (auxiliary != null)
{
// Compare first linked list node to second linked list node value
while (deviation != null)
{
if (deviation.data == auxiliary.data)
{
// increase resultant count by 1
// Print common node
print("  " + auxiliary.data);
// Like a break operation
deviation = null;
// Active state because we are got similar node
status = true;
counter += 1;
}
else
{
// Visit to next node
deviation = deviation.next;
}
}
// Visit to next node
auxiliary = auxiliary.next;
// Start to first node of second linked list
}
if (status == false)
{
// When no common node exists
print(" None \n");
}
else
{
print("\n Total common element is : " + counter + "\n");
}
}
}
fun main(args: Array < String > ): Unit
{
var sll1: SingleLL = SingleLL();
var sll2: SingleLL = SingleLL();
//  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
//  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll1.findCommonNodes(sll2);
}``````

#### Output

`````` Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL

Common Value
3  8  -2  9
Total common element is : 4``````

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 