Intersection Point of Two Linked Lists in C++.

Given head nodes of two singly Linked List. Somehow, both the linked lists intersected at one point and we need to return the intersection of those two linked lists. If there is no intersection point between two linked lists then you can return a NULL.

Note: There is no circle present in the structure of two linked lists and you are not allowed to make any changes to the original structure of the linked list. (alert-passed)

Approach 1: Brute Force (using two nested loops).

Run two nested loops where the outer loop is for the first list and the inner loop is for the second list. You need to check that for at least one current node of the first list there exists one same node that is present in the second list. The time complexity of this algorithm is O(m*n) where m and n are the numbers of nodes present in both lists.

C++ Solution Code:

/*C++ Program to find Intersection of Two Linked List*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to find intersection of two linked list
ListNode *findIntersection(ListNode *head1, ListNode *head2){

    while(head2){
        ListNode *temp = head1;
        while(temp){
            if(temp == head2)
              return head2;
            temp = temp->next;  
        }
        head2 = head2->next;
    }
    return NULL;
}
int main(){
    /*
    1st Linked List: 4->1->5->3->4
    2nd Linked List: 5->2->1->5->3->4
    Both are intersecting at 5
    */
    ListNode *head1 = new ListNode(4);
    head1->next = new ListNode(1);
    ListNode *commonNode;
    commonNode = new ListNode(5);
    commonNode->next = new ListNode(3);
    commonNode->next->next = new ListNode(4);
    head1->next->next = commonNode;

    ListNode *head2 = new ListNode(5);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(1);
    head2->next->next->next = commonNode;

    cout<<"Linked List1: ";
    printList(head1);

    cout<<"\nLinked List2: ";
    printList(head2);

    ListNode *intersect = findIntersection(head1, head2);

    if(intersect == NULL)
       cout<<"\nNo Intersection Found!";
    else
       cout<<"\nIntersect at: "<<intersect->data;

    return 0;
}

Output:

Linked List1: 4 1 5 3 4
Linked List2: 5 2 1 5 3 4 
Intersect at: 5

Time Complexity: O(m*n) where m and n are the numbers of nodes in both lists.
Space Complexity: O(1)

Approach 2: Two Pointer Approach.

Follow the steps given below:

Declare two pointers p1 and p2 and initialize them with head1 and head2.
Traverse both the list using p1 and p2 one node at a time.
When p1 reaches the end of the list then reassign it to head2.
Similarly when p2 reaches the end of the list then reassign it to head1.
Reassigning both the pointer will put them at an equal distance from the intersection point.
In the second iteration, if both the pointer meet each other then return the intersection point else return NULL.

C++ Solution Code:

/*C++ Program to find Intersection of Two Linked List
using two pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}

//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to find intersection of two linked list
ListNode *findIntersection(ListNode *head1, ListNode *head2){

    ListNode* p1 = head1;
    ListNode* p2 = head2;

    while(p1 != NULL && p2 != NULL && p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
            
        if(p1 == p2){
            return p1;
        }
        if(p1 == NULL) p1 = head2;
        if(p2 == NULL) p2 = head1;
    }
    return p1;
}
int main(){
    /*
    1st Linked List: 4->1->5->3->4
    2nd Linked List: 5->2->1->5->3->4
    Both are intersecting at 5
    */
    ListNode *head1 = new ListNode(4);
    head1->next = new ListNode(1);
    ListNode *commonNode;
    commonNode = new ListNode(5);
    commonNode->next = new ListNode(3);
    commonNode->next->next = new ListNode(4);
    head1->next->next = commonNode;

    ListNode *head2 = new ListNode(5);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(1);
    head2->next->next->next = commonNode;

    cout<<"Linked List1: ";
    printList(head1);

    cout<<"\nLinked List2: ";
    printList(head2);

    ListNode *intersect = findIntersection(head1, head2);

    if(intersect == NULL)
       cout<<"\nNo Intersection Found!";
    else
       cout<<"\nIntersect at: "<<intersect->data;

    return 0;
}

Output:

Linked List1: 4 1 5 3 4
Linked List2: 5 2 1 5 3 4 
Intersect at: 5

Time Complexity: O(m+n) where m and n are the numbers of nodes in both lists.
Space Complexity: O(1)

Next:

(getButton) #text=(Merge Two Sorted Linked List) #icon=(link) #color=(#2339bd)

Intersection Point of Two Linked Lists in C++.

No comments:

Post a Comment