package test;
public class GetFirstCommonNode {
class ListNode{
public String key;
public ListNode next;
}
public ListNode findFirstCommonNode(ListNode headOne, ListNode headTwo){
if(headOne == null || headTwo == null){
return null;
}
int length1 = getListLength(headOne);
int length2 = getListLength(headTwo);
int lenghtdif = length1 - length2;
ListNode headLong = headOne;
ListNode headShort = headTwo;
if(length2 > length1){
headLong = headTwo;
headShort = headOne;
lenghtdif = length2 - length1;
}
for(int i=0; i<lenghtdif; ++i){
headLong = headLong.next;
}
while((headLong!=null)&&(headShort!=null)&&(headLong!=headShort)){
headLong = headLong.next;
headShort = headShort.next;
}
ListNode firstCommonNode = headLong;
return firstCommonNode;
}
public int getListLength(ListNode head){
int length = 0;
ListNode node = head;
while(node!=null){
++length;
node = node.next;
}
return length;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GetFirstCommonNode node = new GetFirstCommonNode();
ListNode a = node.new ListNode();
a.key = "a";
ListNode b = node.new ListNode();
b.key = "b";
ListNode e = node.new ListNode();
e.key = "e";
ListNode d = node.new ListNode();
d.key = "d";
ListNode f = node.new ListNode();
f.key = "f";
ListNode h = node.new ListNode();
h.key = "h";
f.next = d;
d.next = b;
b.next = a;
h.next = e;
e.next = b;
b.next = a;
ListNode node1 = node.findFirstCommonNode(f, h);
System.out.println(node1.key);
}
}