第一个公共节点,遍历到最后节点后再从另一个开始
两个链表的第一个公共结点
http://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46
第一个公共节点,遍历到最后节点后再从另一个开始。
证明:L1特有的长度为m,L2特有的部分为n,相同长度为t。
则 L1=m+t,L2=n+t;
所以L1+n=L2+m;
所以,至少第二次会匹配!
/**
* 输入两个链表,找出它们的第一个公共结点。
* @param pHead1 链表1
* @param pHead2 链表2
* @return 第一个公共结点
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null){
return null;
}
ListNode cur1=pHead1,cur2=pHead2;
while (cur1!=cur2){
cur1= cur1==null?pHead2:cur1.next;
cur2=cur2==null?pHead1:cur2.next;
}
return cur1;
}
