Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Intersection of Two Linked Lists

Easy
0/40
Average time to solve is 25m
profile
Contributed by
296 upvotes
Asked in companies
MicrosoftAdobeApple

Problem statement

You are given two Singly Linked Lists of integers, which may have an intersection point.

Your task is to return the first intersection node. If there is no intersection, return NULL.


Example:-
The Linked Lists, where a1, a2, c1, c2, c3 is the first linked list and b1, b2, b3, c1, c2, c3 is the second linked list, merging at node c1.

alt.txt

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The input format contains three lines consisting of the front part of the first list, front part of the second list and the intersection part of the lists, respectively.

All lines contain the elements of the singly linked list separated by a single space and terminated by -1.  

So the first line would contain
       a1, a2, ...an, -1. 

Similarly, the second line would contain
       b1, b2, ...bm, -1. 

Similarly, the third line would contain
       c1, c2, ...ck -1. 
Output format :
The only output line contains data from the first merged node if the correct node is returned. If there is no merging or incorrect answer, the output contains -1.

You don't have to print by yourself explicitly. It has been taken care of. You need to return the first merged node.
Sample Input 1 :
4 1 -1
5 6 -1
8 -1
Sample Output 1 :
8
Explanation For Sample Input 1:
As shown in the diagram, the node with data is 8, at which merging starts

Sample Input 1

Sample Input 2 :
1 9 1 -1
3 -1
2 -1
Sample Output 2 :
2
Constraints :
-10^9 <= data <= 10^9 and data != -1
 The length of both the linked list is positive.
 Time Limit: 1 sec
Hint

Two nested loops?

Approaches (3)
Brute Force
  • For each node in the first list, traverse the entire second list
  • Check if any node in the second list coincides with the first list
    • If it does, return that node
    • If it doesn’t, return NULL
Time Complexity

O(N * M), where ‘N’ and ‘M’ are the lengths of the first and second linked lists, respectively. 

 

Since, for each element of the first list, we are traversing for the second list, therefore the time complexity is O(N * M)

Space Complexity

O(1)
 

Since we only use constant space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Intersection of Two Linked Lists
All tags
Sort by
Search icon

Interview problems

C++ Code: TC = O(N+M) SC = O(1)

Node* findIntersection(Node *head1, Node *head2)

{

    //Write your code here

    Node *temp1 = head1;

    Node *temp2 = head2;

 

    bool round1 = false;

    bool round2 = false;

 

    while(temp1 != nullptr && temp2 != nullptr){

        //if node intersect

        if(temp1 == temp2) return temp1;

 

        if(temp1->next == nullptr && round1 == false){

            temp1 = head2;

            round1 = true;

        }

        else temp1 = temp1->next;

 

        if(temp2->next == nullptr && round2 == false){

            round2 = true;

            temp2 = head1;

        }

        else temp2 = temp2->next;

    }

    return nullptr;

}

19 views
0 replies
0 upvotes

Interview problems

JAVA Code : TC = O(N+M) SC = O(1)

public static int findIntersection(Node head1, Node head2) {

        //Write your code here

        Node temp1 = head1;

        Node temp2 = head2;

 

        boolean round1 = false;

        boolean round2 = false;

 

        while(temp1 != null && temp2 != null){

            //if node intersect

            if(temp1 == temp2) return temp1.data;

 

            if(temp1.next == null && round1 == false){

                temp1 = head2;

                round1 = true;

            }

            else temp1 = temp1.next;

 

            if(temp2.next == null && round2 == false){

                round2 = true;

                temp2 = head1;

            }

            else temp2 = temp2.next;

        }

        return -1;

    }

11 views
0 replies
0 upvotes

Interview problems

SOLUTION CPP INTERSECTION


Node* findIntersection(Node *firstHead, Node *secondHead)
{
    //Write your code here
    Node* temp=firstHead;
    Node* temp2=secondHead;
    if(temp==NULL && temp2==NULL) return NULL;
    while (temp!=NULL && temp2!=NULL && temp!=temp2) {
      temp = temp->next;
      temp2 = temp2->next;

      if (temp == temp2)
        return temp;
      if (temp == NULL)
        temp = secondHead;
      if (temp2 == NULL)
        temp2 = firstHead;
    }
    return temp;
}
14 views
0 replies
0 upvotes

Interview problems

INTERSECTION OF LINKED LISTS

We need to traverse throughout both the linkedlist

.

.

.

'''

Following is the structure of the Node class already defined.

 

class Node:

def __init__(self, data):

self.data = data

self.next = None

 

'''

 

def findIntersection(firstHead, secondHead):

# Write your code here.

        l1,l2 = firstHead,secondHead

        while l1 != l2: 

             l1 = l1.next if l1 else secondHead

             l2 = l2.next if l2 else firstHead

return l1

72 views
0 replies
1 upvote

Interview problems

Java Solution

public class Solution {
    public static int findIntersection(Node firstHead, Node secondHead) {

        if(firstHead == null || secondHead == null) return 0;

        Node dummy1 = firstHead;
        Node dummy2 = secondHead;

        while(dummy1 != dummy2){
            dummy1 = dummy1 == null ? secondHead : dummy1.next;
            dummy2 = dummy2 == null ? firstHead : dummy2.next;
        }

        return dummy1.data;
    }
}
114 views
0 replies
0 upvotes

Interview problems

EASY C++ SOLUTION BEATS 100% USING TWO POINTER APPROACH

Node* findIntersection(Node *firstHead, Node *secondHead)

{

    //Write your code here

     Node* p1= firstHead;

        Node* p2= secondHead;

        if (p1 == NULL || p2 == NULL) return NULL;

 

    while (p1 != NULL && p2 != NULL && p1 != p2) {

        p1 = p1->next;

        p2 = p2->next;

 

        //

        // Any time they collide or reach end together without colliding 

        // then return any one of the pointers.

        //

        if (p1 == p2) return p1;

 

        //

        // If one of them reaches the end earlier then reuse it 

        // by moving it to the beginning of other list.

        // Once both of them go through reassigning, 

        // they will be equidistant from the collision point.

        //

        if (p1 == NULL) p1 = secondHead;

        if (p2 == NULL) p2 = firstHead;

    }

        

    return p1;

}

153 views
0 replies
1 upvote

Interview problems

JAVA-OPTIMIZED

/****************************************************************

 

 Following is the class structure of the Node class:

 

 class Node {

     public int data;

     public Node next;

 

     Node()

     {

         this.data = 0;

         this.next = null;

     }

     Node(int data)

     {

         this.data = data;

         this.next = null;+

     }

     Node(int data, Node next)

     {

         this.data = data;

         this.next = next;

     }

 }

 

 *****************************************************************/

import java.util.*;

public class Solution {

    public static int findIntersection(Node firstHead, Node secondHead) {

        if(firstHead==null || secondHead==null)

        {

            return 0;

        }

          Node t1=firstHead;

          Node t2=secondHead;

          while(t1!=t2)

          {

              t1=t1.next;

              t2=t2.next;

              if(t1==t2)

              {

                  return t1.data;

              }

              if(t1==null)

              {

                  t1=secondHead;

              }

              if(t2==null)

              {

                  t2=firstHead;

              }

          }

          return 0;

    }

}

 

java

67 views
0 replies
0 upvotes

Interview problems

Intersection of Two Linked Lists

Node* findIntersection(Node *firstHead, Node *secondHead)

{

    //Write your code here

 

    Node* l1 = firstHead;

    Node* l2 = secondHead;

 

    if(l1 == NULL || l2 == NULL)

    return nullptr;

 

    while(l1 != l2){

        l1 = l1 -> next;

        l2 = l2 -> next;

 

        if(l1 == l2)

        return l2;

 

        if(l1 == NULL)

        l1 = secondHead;

 

        if(l2 == NULL)

        l2 = firstHead;

    }

    return l2;

}

 

215 views
0 replies
0 upvotes

Interview problems

Simple Six Line Java code without finding distance



/****************************************************************

 Following is the class structure of the Node class:

 class Node {
     public int data;
     public Node next;

     Node()
     {
         this.data = 0;
         this.next = null;
     }
     Node(int data)
     {
         this.data = data;
         this.next = null;
     }
     Node(int data, Node next)
     {
         this.data = data;
         this.next = next;
     }
 }

 *****************************************************************/

public class Solution {
    public static int findIntersection(Node firstHead, Node secondHead) {
        //Write your code here
        Node first = firstHead;
        Node second = secondHead;
        while(first!=second){
            first = (first.next!=null)?first.next:secondHead;
            second = (second.next!=null)?second.next:firstHead;
        }
        return first.data;
    }
}
88 views
0 replies
1 upvote

Interview problems

java solution|| using hashSet

import java.util.*;

public class Solution {

    public static int findIntersection(Node firstHead, Node secondHead) {

        //Write your code here

        HashSet<Node> st=new HashSet<>();

        while(firstHead!=null){

            st.add(firstHead);

            firstHead=firstHead.next;

        }

        while(secondHead!=null){

            if(st.contains(secondHead)){

                return secondHead.data;

            }

            secondHead=secondHead.next;

        }

        return 0;

    }

}

67 views
0 replies
0 upvotes
Full screen
Console