双指针:
三种情况:(总长度分别为m,n)
1、存在公共节点:A链表未相交部分为a,相交部分为c
B链表未相交部分为b,相交部分为c
当指针Aa或者指针Bb为null(也就是走到链表的尾部)的时候,重新指向另外一条链表的头节点继续走。
那么两个指针走到公共点的长度是a+c+b和b+c+a,长度一样,得出公共节点
2、不存在公共节点(m!=n):
当指针Aa或者Bb为null的时候,重新指向另外一条链表的头节点继续走。
那么最终会同时为null:两个指针走的长度:m+n和n+m;
3,不存在公共节点(m=n)
那么最终会同时为null:两个指针走的长度:m=n
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null){
return null;
}
ListNode node1 = pHead1;
ListNode node2 = pHead2;
//如果同时出现null,符合2,3种情况
while(node1!=null||node2!=null){
if(node1==null){
node1 = pHead2;
}
else if(node2==null){
node2=pHead1;
}
//第一种情况
if(node1==node2){
return node1;
}
node1=node1.next;
node2=node2.next;
}
return node1;
}

京公网安备 11010502036488号