How to find the intersection point of two linked lists?

The problem statement is:

Given the head pointers (head1 and head2 ) of two linked lists, find the intersection node of the two lists.

Linked-Lists

For the above image, program needs to output: 4 as the intersection point.

Naive Approach

Run two for loops: outer loop from 0 to head1.length() and inner loop from 0 to head2.length(). Match each node of list1 with each node of list2. If there’s a match return node->value.

Pseudocode

Solve (head1, head2)
1. node1 = head1, node2 = head2
2. length1 = head1.size(), length2 = head2.size() 
3.   for i=0 to length1:
4.     for j=0 to length2:
5.       if (node1 == node2) then:
6.         return  node1->value
7.       node2 = node2->next
8.   node1 = head1->next
9.  return null

Time Complexity: O(M*N) [where, M and N be the length of two linked lists respectively]
Auxiliary Space: O(1)

Optimised Approach

Let length1 will be the length of list1 and length2 will be the length of list2. Now assuming length1 > length2. Traverse list1 from head (0) to the difference of the two lists’ length (d = length1 – length2). Now we could traverse both the lists simultaneously to meet the intersection point, since the extra nodes of list1 have already been traversed.

Pseudocode

Solve (head1, head2)
1. node1 = head1, node2 = head2
2. length1 = head1.size(), length2 = head2.size()
3. d = length1 - length2
3. if length1 < length2 then:
4.   node1 = head2
5.   node2 = head1
6.   d = length2 - length1
7. for i=0 to d:
8.   node1 = node1-next
9. while (node1 != node2):
10.  node1 = node1->next
11.  node2 = node2->next
12. return node1    

Time Complexity: O(M + N)
Auxiliary Space: O(1)

Code Implementation

//
//  main.cpp
//  Intersection Point
//
//  Created by Himanshu on 03/10/21.
//


#include <iostream>
using namespace std;

struct node {
    int info = 0;
    struct node *next;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->info = data;
    Node->next = NULL;
 
    return(Node);
}

void printLinkedList (Node* head) {
    Node *x = head;
    
    while (x != NULL) {
        cout<<(x->info)<<" ";
        x = x->next;
    }
    cout<<endl;
}

Node* insertNode (Node *head, Node* x) {
    Node *node = head;
    while (node->next != NULL) {
        node = node->next;
    }
    x->next = NULL;
    node->next = x;
    return head;
}

Node* searchNode (Node *head, int k) {
    Node* x = head;
    
    while (x != NULL && x->info != k) {
        x = x->next;
    }
    
    if (x != NULL && x->info == k) {
        return x;
    } else {
        return NULL;
    }
}

int findListLength (Node *head) {
    int len = 0;
    Node *node = head;
    while (node != NULL) {
        len++;
        node = node->next;
    }
    return len;
}

Node* solve (Node *head1, Node *head2) {
    Node *node1 = head1, *node2 = head2;
    int len1 = findListLength(head1), len2 = findListLength(head2);
    int diff = len1 - len2;
    
    if (len1 < len2) {
        node1 = head2;
        node2 = head1;
        diff = len2 - len1;
    }
    
    for (int i=0; i<diff; i++) {
        node1 = node1->next;
    }
    
    while (node1 != node2) {
        node1 = node1->next;
        node2 = node2->next;
    }
    
    return node1;
}

int main() {
    Node *head1 = newNode(1);
    Node *head2 = newNode(9);
    
    head1 = insertNode (head1, newNode(2));
    head1 = insertNode (head1, newNode(3));
    head1 = insertNode (head1, newNode(4));
    head1 = insertNode (head1, newNode(8));
    
    head2 = insertNode (head2, newNode(5));
    head2 = insertNode (head2, newNode(7));
    
    Node *x = searchNode(head2, 7);
    x->next = searchNode(head1, 4);
    
    cout<<"Linked List 1:"<<endl;
    printLinkedList(head1);
    
    cout<<"Linked List 2:"<<endl;
    printLinkedList(head2);
    
    x = solve(head1, head2);
    
    if (x) {
        cout<<"Intersection point is: "<<(x->info)<<endl;
    } else {
        cout<<"No intersection point found"<<endl;
    }
    
    return 0;
}

Output

Linked List 1:
1 2 3 4 8 
Linked List 2:
9 5 7 4 8 
Intersection point is: 4

Here’s a working example:

https://ideone.com/zwssLW

Leave a Reply

Your email address will not be published.