Write a function to get the intersection point of two Linked Lists

Problem Statement

The problem “Write a function to get the intersection point of two Linked Lists” states that you are given two linked lists. But they are not independent linked lists. They are connected at some point. Now you need to find this point of intersection of these two lists.

Example

1 -> 2
      \
        5 -> 6
      /
3 -> 4

Point of intersection: 5

Explanation: There are two linked lists shown in the input which are 1, 2, 5, 6 and 3, 4, 5, 6. Both of them are merged at the node whose value is 5. Thus the output is 5.

Approach

The problem is simple to describe. There are two linked lists but they are joined or interconnected at some point. Before the joining point, both the linked lists have different nodes and after the joining node. They are represented by a single list. So, the problem is how do we find such a node(or point)? There may be many possible answers/solutions to the problem. But the most simple way is to find the lengths of the linked lists. Whenever a solution is simple, it is not efficient enough to pass the time limit. But that is not the case here. This solution is efficient and simple.

Explanation

In this solution, we are going to find the lengths of the two linked lists. And then we going to move the head of the longer linked list ahead by (lenA – lenB) nodes. Here lenA and lenB denote the length of linked list A and B respectively. But why did we do this?

Consider the length of the common linked list is z, the length of the longer list is x + z and that of the shorter linked list is y + z. So until now, we have moved lenA – lenB over the longer linked list. That is (x + z – (y + z)) = x – y. This means we have moved over the longer linked list until the node at which we are currently standing also has length y from the joining node as that of the head of the shorter linked list. Then we move simultaneously on both the linked lists and check if both the current nodes are equal. If so, we have found our intersection point. But if we don’t find any such point until the end of the linked lists. Then this indicates that they do not have an intersection point.

So this is how we write a function to get the intersection point of two Linked Lists.

Code

C++ code to find the intersection of two linked lists

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}

Intersection at node: 5

Java code to find the intersection of two linked lists

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}

Intersection at node: 5

Complexity Analysis

Time Complexity

O(N), since we have run over each of the nodes in the linked lists exactly once. If there exists an intersection point then as we reach that node we return it. Else each node is traversed only once. This proves that the time complexity is linear.

Space Complexity

O(1), the only thing that we have stored is the length of the linked lists which makes this algorithm take only constant space.