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.




Comment

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







© 2022, kalkicode.com, All rights reserved