Intersection of two Sorted Linked Lists

Intersection of two linked list are all similar nodes which are exist in both linked list. Let see an example.

Intersection of two Sorted Linked Lists

Here given code implementation process.

//C Program
//Intersection of two Sorted Linked Lists
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=NULL;
    if(*head==NULL){
      *head=node;
    }else{
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  while(temp!=NULL){
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
//Find intersection of two given linked list
void intersection(struct Node*head1,struct Node *head2){

  if(head1==NULL || head2 ==NULL){
    return;
  }else{

    while(head1!=NULL && head2!=NULL){

      if(head1->data==head2->data){
        //when found same node
        printf("%d  ",head1->data);
        //Visites next upcoming node
        head1=head1->next;
        head2=head2->next;

      }else if(head1->data>head2->data){
        head2=head2->next;
      }else{
        head1=head1->next;
      }
    }
  }
}
int main(){
  //create node pointer
  struct Node*head1=NULL,*head2=NULL;
  //insert element of linked list
  insert(&head1,0);
  insert(&head1,1);
  insert(&head1,2);
  insert(&head1,3);
  insert(&head1,7);
  insert(&head1,11);
  insert(&head1,21);

  //Create second linked list
  insert(&head2,1);
  insert(&head2,3);
  insert(&head2,7);
  insert(&head2,11);
  insert(&head2,16);
  insert(&head2,17);
  printf("First Linked List \n");
  display(head1);
  printf("\nSecond Linked List \n");
  display(head2);
  printf("\nIntersection \n");
  intersection(head1,head2);
  return 0;
}

Output

First Linked List 
0  1  2  3  7  11  21  
Second Linked List 
1  3  7  11  16  17  
Intersection 
1  3  7  11
//C++ Program 
//Intersection of two Sorted Linked Lists
#include<iostream>
using namespace std;

//create structure
struct Node
{
	int data;
	struct Node*next;
};
class LinkedList
{

public:
    Node*head;//head node
    LinkedList();
    void insert(int);
    void display();
    void intersection(Node*);
};
LinkedList::LinkedList()
{
	head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value)
{
    //Create dynamic node
	struct Node*node=new Node;
	if(node==NULL)
	{
		cout<<"Memory overflow\n";
	}else
	{
		node->data=value;
		node->next=NULL;
		if(head==NULL)
		{
      		//Base condition
			head=node;
		}else
		{
			Node*temp=head;
			while(temp->next!=NULL)
			{
				temp=temp->next;
			}
      		//Add newly node at last
			temp->next=node;
		}
	}
}
//Display all node value in linked list
void LinkedList:: display()
{
	if(head==NULL)
	{
		cout<<"Empty linked list";
	}
	else
	{
		Node*temp=head;

		while(temp!=NULL)
		{
      		//print node value
			cout<<temp->data<<" ";
			temp=temp->next;
		}
	}

}
//Find intersection of two given linked list
void LinkedList :: intersection(Node*head2)
{
	Node *head1=head;
	if(head1==NULL || head2==NULL)
	{
		//When any one linked list are empty
		return ;
	}
	else
	{
		while(head1 != NULL && head2 != NULL)
		{
			if(head1->data == head2->data)
			{
				cout<<head1->data<<" ";
        		//Visites next upcoming node
				head1=head1->next;
				head2=head2->next;

			}else if(head1->data>head2->data)
			{
				//head2 is moving to next node 
				head2=head2->next;

			}else
			{
				//head1 is moving to next node 
				head1=head1->next;
			}
		}
	}
}
int main()
{

    //create object
	LinkedList obj1=LinkedList()
	,obj2=LinkedList();
    //Add element into first linked list
	obj1.insert(0);
	obj1.insert(1);
	obj1.insert(2);
	obj1.insert(3);
	obj1.insert(7);
	obj1.insert(11);
	obj1.insert(21);

    //Add element into second linked list
	obj2.insert(1);
	obj2.insert(3);
	obj2.insert(7);
	obj2.insert(11);
	obj2.insert(16);
	obj2.insert(17);


    //display all node
	cout<<"Fist Linked List : "<<endl;
	obj1.display();
	cout<<"\nSecond Linked List : "<<endl;
	obj2.display();
	cout<<"\nIntersection : "<<endl;
	obj1.intersection(obj2.head);
}

Output

Fist Linked List : 
0 1 2 3 7 11 21 
Second Linked List : 
1 3 7 11 16 17 
Intersection : 
1 3 7 11
//Java Program
//Intersection of two Sorted Linked Lists
public class LinkedList{

  static class Node{
    int data;
    Node next;
  }
  public Node head;
  //Class constructors
  LinkedList(){
    head=null;
  } 
  //insert element
  public void insert(int value){
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(this.head==null) this.head=node;
    else{
      Node temp=this.head;
      //find last node
      while(temp.next!=null){
        temp=temp.next;
      }
      temp.next=node;
    }
    
  }
  //Display all Linked List elements
  public void display(){
    if(this.head!=null){
      
      Node temp=this.head;
      while(temp!=null){
        System.out.print(temp.data+"  ");
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }
  public void intersection(Node head2){
  Node head1=this.head;
  if(head1==null || head2==null){
    return ;
  }
  else{
    while(head1!=null && head2!=null){
      if(head1.data==head2.data){
        System.out.print(head1.data+"  ");
        //Visites next upcoming node
        head1=head1.next;
        head2=head2.next;
      }else if(head1.data>head2.data){
        head2=head2.next;
      }else{
        head1=head1.next;
      }
    }
  }
}
  public static void main(String[] args) {
    
    LinkedList obj1=new LinkedList();
    obj1.insert(0);
    obj1.insert(1);
    obj1.insert(2);
    obj1.insert(3);
    obj1.insert(7);
    obj1.insert(11);
    obj1.insert(21);

   LinkedList obj2=new LinkedList();
    obj2.insert(1);
    obj2.insert(3);
    obj2.insert(7);
    obj2.insert(11);
    obj2.insert(16);
    obj2.insert(17);

    System.out.println("Fist List Element :");
    obj1.display();

    System.out.println("\nSecond List Element :");
    obj2.display();
    System.out.println("\nIntersection :");
    obj1.intersection(obj2.head);

  }
}

Output

0  1  2  3  7  11  21  
Second List Element :
1  3  7  11  16  17  
Intersection :
1  3  7  11
#Python Program
#Intersection of two Sorted Linked Lists
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node

    def display(self):
        if(self.head==None):
            print("Empty Linked List")
            return

        temp=self.head
        
        while(temp!=None):
          print(temp.data,end=" ")
          temp=temp.next
        print("\n")

    def  intersection(self,head2):
      head1=self.head
      if(head1==None or head2==None):
        return 
      else:
        while(head1!=None and head2!=None):
          if(head1.data==head2.data):
            print(head1.data,end=" ")
            #Visites next upcoming node
            head1=head1.next
            head2=head2.next
          elif(head1.data>head2.data):
            head2=head2.next
          else:
            head1=head1.next

def main():
 
    obj1=Linked()
    #insert node in 1st Linked List
    obj1.insert(0)
    obj1.insert(1)
    obj1.insert(2)
    obj1.insert(3)
    obj1.insert(7)
    obj1.insert(11)
    obj1.insert(21)

    obj2=Linked()
    obj2.insert(1)
    obj2.insert(3)
    obj2.insert(7)
    obj2.insert(11)
    obj2.insert(16)
    obj2.insert(17)
    print("First Linked List Elements : ")
    obj1.display()
    print("Second Linked List Elements : ")
    obj2.display()
    print("Intersection : ")
    obj1.intersection(obj2.head)

if __name__=="__main__":
    main()

Output

First Linked List Elements : 
0 1 2 3 7 11 21 

Second Linked List Elements : 
1 3 7 11 16 17 

Intersection : 
1 3 7 11
Python
//C# Program
//Intersection of two Sorted Linked Lists
using System;
//node class
public class Node{
	public  int data;
	public  Node next;
}
class LinkedList
{
	Node head;
	public LinkedList(){
		head=null;
	}
	//insert node of linked list
	public void insert(int data){
		Node newNode=new Node();
		newNode.data=data;
		newNode.next=null;
		if(head==null) head=newNode;
		else{
			Node temp=head;
			//get last node
			while(temp.next!=null){
				temp=temp.next;
			}
			//add new node
			temp.next=newNode;
		}
	}
	//display linked list nodes value
	public void display(){
		if(head==null){
			Console.Write("Empty List");
		}else{
			Node temp=head;
			while(temp!=null){
				Console.Write("  {0}",temp.data);
				temp=temp.next;
			}

		}
	}
	//Find intersection of two given linked list
	public void intersection(Node head2){
		Node head1=this.head;
		if(head1==null || head2==null){
			return ;
		}
		else{
			while(head1!=null && head2!=null){
				if(head1.data==head2.data){
					Console.Write("  {0}",head1.data);
					//Visites next upcoming node
					head1=head1.next;
					head2=head2.next;
				}else if(head1.data>head2.data){
					head2=head2.next;
				}else{
					head1=head1.next;
				}
			}
		}
	}
	static void Main()
	{
		LinkedList obj1=new LinkedList();
		obj1.insert(0);
		obj1.insert(1);
		obj1.insert(2);
		obj1.insert(3);
		obj1.insert(7);
		obj1.insert(11);
		obj1.insert(21);

		LinkedList obj2=new LinkedList();
		obj2.insert(1);
		obj2.insert(3);
		obj2.insert(7);
		obj2.insert(11);
		obj2.insert(16);
		obj2.insert(17);

		Console.WriteLine("Fist Linked List  :");
		obj1.display();

		Console.WriteLine("\nSecond Linked List Element :");
		obj2.display();
		Console.WriteLine("\nIntersection :");
		obj1.intersection(obj2.head);
	}
}

Output

Fist Linked List  :
  0  1  2  3  7  11  21
Second Linked List Element :
  1  3  7  11  16  17
Intersection :
  1  3  7  11
<?php
//Php program 
//Intersection of two Sorted Linked Lists
class Node
{
	public $data;
	public $next;
	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class LinkedList{

	public $head;
	function __construct()
	{
		$head=NULL;
	}
    /*
    * Append the Given data value at end of linked list
    * Fun : insert
    * Parm: data value
    *@return None
    */
    function insert($data)
    {
    	$newNode=new Node($data); 
    	if($this->head==NULL)
    	{
    		$this->head=$newNode;
    	}else{
    		$temp=$this->head;
            //find last node of linked list
    		while($temp->next!=NULL){
    			$temp=$temp->next;
    		}
            //add new node to last of linked list
    		$temp->next=$newNode;
    	}
    }
    //Display all inserted node in linked list
    function display()
    {
    	if($this->head==NULL)
    	{
    		echo "Empty Linked List";
    	}
    	else{
    		$temp=$this->head;
    		
    		while($temp!=NULL){
                //display node value
    			echo "  ".$temp->data;
                $temp=$temp->next; //visit to next node
            }
        }   
    }

    
    //Find intersection of two given linked list
    function intersection($head2)
    {
    	$head1=$this->head;	
    	if($head1==NULL || $head2 ==NULL){
    		return;
    	}else{

    		while($head1!=NULL && $head2!=NULL){

    			if($head1->data==$head2->data){
        			//when found same node
    				echo ($head1->data." ");
        			//Visites next upcoming node
    				$head1=$head1->next;
    				$head2=$head2->next;

    			}else if($head1->data>$head2->data){
    				$head2=$head2->next;
    			}else{
    				$head1=$head1->next;
    			}
    		}
    	}
    }
}
function main(){
  //Make a object of LinkedList class
	$obj1= new LinkedList();


	$obj1->insert(0);
	$obj1->insert(1);
	$obj1->insert(2);
	$obj1->insert(3);
	$obj1->insert(7);
	$obj1->insert(11);
	$obj1->insert(21);

	$obj2=new LinkedList();
	$obj2->insert(1);
	$obj2->insert(3);
	$obj2->insert(7);
	$obj2->insert(11);
	$obj2->insert(16);
	$obj2->insert(17);

	echo("Fist List Element :");
	$obj1->display();

	echo ("\nSecond List Element :");
	$obj2->display();
	echo ("\nIntersection :");
	$obj1->intersection($obj2->head);
}
main();
?>

Output

Fist List Element :  0  1  2  3  7  11  21
Second List Element :  1  3  7  11  16  17
Intersection :1 3 7 11

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved