面试题37：两个链表的第一个公共结点

  package offer;
public class  {
	static class ListNode{
		int data;
		ListNode  next;
		public ListNode(int data,ListNode next) {
			this.data=data;
			this.next=next;
		}
	}
	
	private int size(ListNode node){
		int count=0;
		if(node==null) return -1;
		ListNode d=node;
		
		while(d!=null){
			count++;
			d=d.next;
		}
		return count;
	}
	
	public ListNode getFirstSameNode(ListNode node1,ListNode node2){
		int l1=size(node1);
		int l2=size(node2);
		ListNode p1 = node1;  
        ListNode p2 = node2;
		if(l1>l2){
			for(int i=0;i<l1-l2;i++){
				p1=p1.next;
			}
			while(p1!=null &&p2!=null &&p1!=p2){
				p1=p1.next;
				p2=p2.next;
			}
			return p1;
		}else{
			for(int i=0;i<l2-l1;i++){
				p2=p2.next;
			}
			while(p1!=null &&p2!=null &&p1!=p2){
				p1=p1.next;
				p2=p2.next;
			}
			return p2;
		}
	}
	
	public static void main(String[] args) {
		ListNode n6=new ListNode(6,null);
		ListNode n5=new ListNode(5,n6);
		ListNode n4=new ListNode(4,n5);
		ListNode n3=new ListNode(3,n4);
		ListNode n2=new ListNode(2,n3);
		ListNode n1=new ListNode(1,n2);
		ListNode l3=new ListNode(3,n4);
		ListNode l2=new ListNode(2,l3);
		
		t37 t=new t37();
		System.out.println(t.getFirstSameNode(n1, l2).data);
	}
}