BM10. [两个链表的第一个公共结点]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM10. 两个链表的第一个公共结点
题目分析
题目也非常的好玩，思路其实就是各自遍历，到达终点之后从对方的起始节点开始遍历，如果有公共节点，那么交换两次次之后必然能够遇到。
看图其实更容易理解
做法分析
判断如果任意一方为空，那么公共节点就是null
if(pHead1 == null || pHead2 == null)
return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int change = 0;
设置p1遍历节点，设置p2遍历节点，如果p1==p2证明当前节点就是公共节点，循环过程如果为空，就将对方的头节点赋值给当前节点，设置交换次数标识计数器change，如果大于两次终止循环。跳出循环没有找到所以返回值为null
int change = 0;
while(true){
if(p1 == p2)
return p1;
p1 = p1.next;
p2 = p2.next;
if(p1 == null){
p1 = pHead2;
change++;
}
if(p2 == null){
p2 = pHead1;
change++;
}
if(change > 2)
break;
}
return null;
完整题解
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null)
return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int change = 0;
while(true){
if(p1 == p2)
return p1;
p1 = p1.next;
p2 = p2.next;
if(p1 == null){
p1 = pHead2;
change++;
}
if(p2 == null){
p2 = pHead1;
change++;
}
if(change > 2)
break;
}
return null;
}
复杂度分析
时间复杂度：，交换两次节点之后肯定相遇，不过查过
，所以时间复杂度是
空间复杂度：，没有使用额外的空间
