Find Intersection Point in Two Linked List

+1 vote
38 views
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 = ?
asked Sep 15, 2017

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;
}
}

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){
}
}

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

public class LinkedListTest {

/**
* @param args
*/
public static void main(String[] args) {

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());

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
answered Sep 15, 2017 by (3,480 points)
//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;
}
answered Jan 18, 2018 by (3,480 points)