Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists:

A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3

begin to intersect at node c1.

解题思路：

先遍历两个list的长度，然后长的减去短的，之后同时遍历即可，JAVA实现如下：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if(headA==null||headB==null)        	return null;        int lengthA=0,lengthB=0;        ListNode tempA=headA,tempB=headB;    	while(tempA!=null){    		tempA=tempA.next;    		lengthA++;        }    	while(tempB!=null){    		tempB=tempB.next;    		lengthB++;        }    	if(lengthB>lengthA){    		tempA=headA;    		headA=headB;    		headB=tempA;    		int temp=lengthA;    		lengthA=lengthB;    		lengthB=temp;    	}    	int length=lengthA-lengthB;    	while(length-->0)    		headA=headA.next;    	while(headA!=null){    		if(headA==headB)    			return headA;    		headA=headA.next;    		headB=headB.next;    	}    	return headA;     }