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
---------
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
Output : [3 8 -2 9]
Example B
---------
Linked List 1
2 → 11 → 2 → 4 → NULL
Linked List 2
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
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// 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->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Add new Node at end of linked list
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
appendNode(sll, node);
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
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)
{
if (sll1->head == NULL || sll2->head == NULL)
{
return;
}
// Display linked list
printf(" Linked List 1 \n");
display(sll1);
// Display linked list
printf(" Linked List 2 \n");
display(sll2);
printf("\n Common Value \n");
// Get first node of both linked list
struct LinkNode *auxiliary = sll1->head;
struct LinkNode *deviation = sll2->head;
// Define some counter variables
int status = 0;
int counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = sll2->head;
}
if (status == 0)
{
// When no common node exists
printf(" None \n");
}
else
{
printf("\n Total common element is : %d\n", counter);
}
}
int main()
{
struct SingleLL *sll1 = newLinkedList();
struct SingleLL *sll2 = newLinkedList();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
addNode(sll1, 3);
addNode(sll1, 11);
addNode(sll1, 8);
addNode(sll1, 5);
addNode(sll1, -2);
addNode(sll1, 16);
addNode(sll1, 9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
addNode(sll2, 4);
addNode(sll2, 9);
addNode(sll2, 7);
addNode(sll2, 3);
addNode(sll2, 8);
addNode(sll2, 6);
addNode(sll2, -2);
findCommonNodes(sll1, sll2);
return 0;
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
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)
{
if (this.head == null || second.head == null)
{
return;
}
// Display linked list
System.out.print(" Linked List 1 \n");
this.display();
// Display linked list
System.out.print(" Linked List 2 \n");
second.display();
System.out.print("\n Common Value \n");
// Get first node of both linked list
LinkNode auxiliary = this.head;
LinkNode deviation = second.head;
// Define some counter variables
boolean status = false;
int counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public: LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
// Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Find common nodes
void findCommonNodes(SingleLL second)
{
if (this->head == NULL || second.head == NULL)
{
return;
}
// Display linked list
cout << " Linked List 1 \n";
this->display();
// Display linked list
cout << " Linked List 2 \n";
second.display();
cout << "\n Common Value \n";
// Get first node of both linked list
LinkNode *auxiliary = this->head;
LinkNode *deviation = second.head;
// Define some counter variables
bool status = false;
int counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
return 0;
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
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)
{
if (this.head == null || second.head == null)
{
return;
}
// Display linked list
Console.Write(" Linked List 1 \n");
this.display();
// Display linked list
Console.Write(" Linked List 2 \n");
second.display();
Console.Write("\n Common Value \n");
// Get first node of both linked list
LinkNode auxiliary = this.head;
LinkNode deviation = second.head;
// Define some counter variables
Boolean status = false;
int counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class SingleLL
{
public $head;
public $tail;
function __construct()
{
$this->head = null;
$this->tail = null;
}
// Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != null)
{
echo " ". $temp->data ." →";
// Visit to next node
$temp = $temp->next;
}
echo " NULL\n";
}
// Find common nodes
public function findCommonNodes($second)
{
if ($this->head == null || $second->head == null)
{
return;
}
// Display linked list
echo " Linked List 1 \n";
$this->display();
// Display linked list
echo " Linked List 2 \n";
$second->display();
echo "\n Common Value \n";
// Get first node of both linked list
$auxiliary = $this->head;
$deviation = $second->head;
// Define some counter variables
$status = false;
$counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
$deviation = $second->head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
$sll1->addNode(3);
$sll1->addNode(11);
$sll1->addNode(8);
$sll1->addNode(5);
$sll1->addNode(-2);
$sll1->addNode(16);
$sll1->addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
$sll2->addNode(4);
$sll2->addNode(9);
$sll2->addNode(7);
$sll2->addNode(3);
$sll2->addNode(8);
$sll2->addNode(6);
$sll2->addNode(-2);
$sll1->findCommonNodes($sll2);
}
main();
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = this.head;
//iterating linked list elements
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)
{
if (this.head == null || second.head == null)
{
return;
}
// Display linked list
process.stdout.write(" Linked List 1 \n");
this.display();
// Display linked list
process.stdout.write(" Linked List 2 \n");
second.display();
process.stdout.write("\n Common Value \n");
// Get first node of both linked list
var auxiliary = this.head;
var deviation = second.head;
// Define some counter variables
var status = false;
var counter = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
main();
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# Find common nodes
def findCommonNodes(self, second) :
if (self.head == None or second.head == None) :
return
# Display linked list
print(" Linked List 1 ")
self.display()
# Display linked list
print(" Linked List 2 ")
second.display()
print("\n Common Value ")
# Get first node of both linked list
auxiliary = self.head
deviation = second.head
# Define some counter variables
status = False
counter = 0
# iterating linked list elements
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
# Reset second linked position
# Start to first node of second linked list
deviation = second.head
if (status == False) :
# When no common node exists
print(" None ")
else :
print("\n Total common element is : ", counter )
def main() :
sll1 = SingleLL()
sll2 = SingleLL()
# First linked list
# 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3)
sll1.addNode(11)
sll1.addNode(8)
sll1.addNode(5)
sll1.addNode(-2)
sll1.addNode(16)
sll1.addNode(9)
# Second linked list
# 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4)
sll2.addNode(9)
sll2.addNode(7)
sll2.addNode(3)
sll2.addNode(8)
sll2.addNode(6)
sll2.addNode(-2)
sll1.findCommonNodes(sll2)
if __name__ == "__main__": main()
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class SingleLL
# Define the accessor and reader of class SingleLL
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL\n")
end
# Find common nodes
def findCommonNodes(second)
if (self.head == nil || second.head == nil)
return
end
# Display linked list
print(" Linked List 1 \n")
self.display()
# Display linked list
print(" Linked List 2 \n")
second.display()
print("\n Common Value \n")
# Get first node of both linked list
auxiliary = self.head
deviation = second.head
# Define some counter variables
status = false
counter = 0
# iterating linked list elements
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
# Reset second linked position
# Start to first node of second linked list
deviation = second.head
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()
# First linked list
# 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3)
sll1.addNode(11)
sll1.addNode(8)
sll1.addNode(5)
sll1.addNode(-2)
sll1.addNode(16)
sll1.addNode(9)
# Second linked list
# 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4)
sll2.addNode(9)
sll2.addNode(7)
sll2.addNode(3)
sll2.addNode(8)
sll2.addNode(6)
sll2.addNode(-2)
sll1.findCommonNodes(sll2)
end
main()
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null, null);
}
// Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Find common nodes
def findCommonNodes(second: SingleLL): Unit = {
if (this.head == null || second.head == null)
{
return;
}
// Display linked list
print(" Linked List 1 \n");
this.display();
// Display linked list
print(" Linked List 2 \n");
second.display();
print("\n Common Value \n");
// Get first node of both linked list
var auxiliary: LinkNode = this.head;
var deviation: LinkNode = second.head;
// Define some counter variables
var status: Boolean = false;
var counter: Int = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
// Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Find common nodes
func findCommonNodes(_ second: SingleLL)
{
if (self.head == nil || second.head == nil)
{
return;
}
// Display linked list
print(" Linked List 1 ");
self.display();
// Display linked list
print(" Linked List 2 ");
second.display();
print("\n Common Value ");
// Get first node of both linked list
var auxiliary: LinkNode? = self.head;
var deviation: LinkNode? = second.head;
// Define some counter variables
var status: Bool = false;
var counter: Int = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
main();
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
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
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
fun addNode(data: Int): Unit
{
var node: LinkNode = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Find common nodes
fun findCommonNodes(second: SingleLL): Unit
{
if (this.head == null || second.head == null)
{
return;
}
// Display linked list
print(" Linked List 1 \n");
this.display();
// Display linked list
print(" Linked List 2 \n");
second.display();
print("\n Common Value \n");
// Get first node of both linked list
var auxiliary: LinkNode ? = this.head;
var deviation: LinkNode ? = second.head;
// Define some counter variables
var status: Boolean = false;
var counter: Int = 0;
// iterating linked list elements
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;
// Reset second linked position
// Start to first node of second linked list
deviation = second.head;
}
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();
// First linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
sll1.addNode(3);
sll1.addNode(11);
sll1.addNode(8);
sll1.addNode(5);
sll1.addNode(-2);
sll1.addNode(16);
sll1.addNode(9);
// Second linked list
// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
sll2.addNode(4);
sll2.addNode(9);
sll2.addNode(7);
sll2.addNode(3);
sll2.addNode(8);
sll2.addNode(6);
sll2.addNode(-2);
sll1.findCommonNodes(sll2);
}
Output
Linked List 1
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
Linked List 2
4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
Common Value
3 8 -2 9
Total common element is : 4
Better solution, Using of set we are easily detect intersection (common) nodes of two linked lists.
-
1) Intersection of two linked lists in java
2) Intersection of two linked lists in c++
3) Intersection of two linked lists in golang
4) Intersection of two linked lists in c#
5) Intersection of two linked lists in vb.net
6) Intersection of two linked lists in php
7) Intersection of two linked lists in node js
8) Intersection of two linked lists in python
9) Intersection of two linked lists in ruby
10) Intersection of two linked lists in scala
11) Intersection of two linked lists in swift
12) Intersection of two linked lists in kotlin
13) Intersection of two linked lists in typescript
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