Intersection of Two Linked Lists Java Program - The Coding Shala

Home >> Interview Questions >> Intersection of Two Linked Lists

The intersection of Two Linked Lists


Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Intersection of Two Linked List - The Coding Shala

begin to intersect at node c1.

Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

The intersection of Two Linked List Java Program

Approach 1:
We can use two loops.
Time Complexity O(size1 * size2).

Java Code 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        while(headA != null){
            ListNode tmp = headB;
            while(tmp != null){
                if(tmp == headA) return headA;
                tmp = tmp.next;
            }
            headA = headA.next;
        }
        return null;
    }
}

Approach 2:
We can use the Hash Table. First, we store every node of the first linked list to the Hash table then check with the second linked list.

Time Complexity : O(size1 + size2).
Space Complexity: O(size1) or O(size2).

Java Code 


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> map = new HashSet<ListNode>();
        while(headA != null){
            map.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(map.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

Approach 3:
We know that after the intersection point length of both the linked list is the same but before this length can be the same or not. Now if you find out the difference between the length and start from the same length then this can be solved in O(n) time.

We traverse both the linked list and when first linked list reach to null then point it to second linked list's head and same we do with the second linked list when it reaches to null assign it to the first's head. when both linked list's node match we return it.

Java Code 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode first = headA;
        ListNode second = headB;
        
        while(first != second){
            if(first == null) first = headB;
            else first = first.next;
            if(second == null) second = headA;
            else second = second.next;
        }
        return first;
    }
}

Approach 4:
First, we find out the length of both linked lists. We know after the intersection length is the same as both the lists.
Java Program: 

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB == null) return null;
        int count1=0,count2=0;
        ListNode tmpA=headA,tmpB=headB;
        while(tmpA!=null){
            count1++;
            tmpA=tmpA.next;
        }
        while(tmpB!=null){
            count2++;   
            tmpB=tmpB.next;
        }
        int diff=Math.abs(count1-count2);
        tmpA=headA;
        tmpB=headB;
        int len = 0;
        if(count1>count2){
            len = count1;
            for(int i=0;i<diff;i++) tmpA=tmpA.next;
        } else if(count2>count1){
            len = count2;
            for(int i=0;i<diff;i++) tmpB=tmpB.next;
        }
        while(tmpA != tmpB){
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
        return tmpA;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala