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