Question

Find Intersection Point in Two Linked List

Node 1 = [1 15 20 30 40 50 60 ]
Node 2 = [5 10 18 20 30 40 50 60 ]

Intersection = ?

Answer 1

package com.ds.linkedlist;

public class Node<T> {

    private T data;
    private Node<T> next;
   
    public Node(){
        setData(null);
        setNext(null);
    }
   
    public Node(T data){
        setData(data);
        setNext(null);
    }
   
    public T getData(){
        return data;
    }
   
    public void setData(T data){
        this.data = data;
    }
   
    public Node<T> getNext(){
        return next;
    }
   
    public void setNext(Node<T> next){
        this.next = next;
    }
}
package com.ds.linkedlist;

public class SingleLinkedList<T> {
    Node<T> head = null;
    public void getIntersectionPoint(SingleLinkedList<Integer> list1, SingleLinkedList<Integer> list2) {
        boolean intsctFound = false;
        Node firstNode = list1.head;
        Node secondNode = list2.head;
        if(list1.getNodeLength() > list2.getNodeLength()){
            int diff = list1.getNodeLength() - list2.getNodeLength();
            while(diff!=0){
                firstNode = firstNode.getNext();
                diff--;
            }
        }else{
            int diff = list2.getNodeLength() - list1.getNodeLength();
            while(diff!=0){
                secondNode = secondNode.getNext();
                diff--;
            }
        }
       
        while(firstNode != null && secondNode != null){
            if(firstNode.getData() == secondNode.getData()){
                intsctFound = true;
                System.out.println("Intersection Found: "+firstNode.getData());
                break;
            }else{
                firstNode = firstNode.getNext();
                secondNode = secondNode.getNext();
            }
        }
       
        if(!intsctFound){
            System.out.println("Intersection Not Found.");
        }
    }

    public void addFirst(T data){
        if(data == null){
            return;
        }
        if(head == null){
            head = new Node<T>(data);
        }else{
            Node<T> newNode = new Node<T>(data);
            newNode.setNext(head);
            head = newNode;
        }
    }
)

package com.ds.linkedlist;

public class LinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
    SingleLinkedList<Integer> list1 = new SingleLinkedList<Integer>();
        list1.addLast(1);
        list1.addLast(15);
        list1.addLast(20);
        list1.addLast(30);
        list1.addLast(40);
        list1.addLast(50);
        list1.addLast(60);
       
        SingleLinkedList<Integer> list2 = new SingleLinkedList<Integer>();
        list2.addLast(5);
        list2.addLast(10);
        list2.addLast(18);
        list2.addLast(20);
        list2.addLast(30);
        list2.addLast(40);
        list2.addLast(50);
        list2.addLast(60);
       
        System.out.print("First List: ");
        list1.getNodeData();
        System.out.println("\nFirst List Length: "+list1.getNodeLength());
       
        System.out.print("\nSecond List: ");
        list2.getNodeData();
        System.out.println("\nSecond List Length: "+list2.getNodeLength());
       
        SingleLinkedList<Integer> singleList = new SingleLinkedList<Integer>();
        singleList.getIntersectionPoint(list1, list2);
    }

}

Output:-

First List: 1 15 20 30 40 50 60
First List Length: 7

Second List: 5 10 18 20 30 40 50 60
Second List Length: 8
Intersection Found: 20

Answer 2

//Time complexity O(mn)
public int findIntersectionPoint(Node list1, Node list2){
        while(list1 != null){
            Node current2 = list2;
            while(current2 != null){
                if(list1.data == current2.data)
                    return list1.data;
                current2 = current2.next;
            }
            list1 = list1.next;
        }
        return -1;
    }