两个链表的第一个公共节点
题解 两个链表有第一个公共节点 我们都从头遍历这两个链表 当遍历完之后 让第一个指针指向第二个链表的头部 第二个指针指向第一个链表的头部 然后继续遍历 即两个链表 一个长 L1 一个长L2 L1 = Y + Z L2 = X + Z 第一次遍历 L1 走了 Y + Z L2 走了X + Z 然后他们交换头节点第二次遍历 如果他们存在这个公共的节点长度Z 即第二次 L1 走 X L2 走了 Y L1 走了 Y + Z + X L2 走了 X + Z + Y 如果他们存在公共节点 如果他们存在公共节点的话 一定会在第二次相遇 相遇的哪个节点就是公共节点 如果没有公共节点 那么他们会在都等于null的时候相等 返回一个null
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null||pHead2 == null) {
return null;
}
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2) {
if(p1 == null) {
p1 = pHead2;
}else {
p1 = p1.next;
}
if(p2 == null) {
p2 = pHead1;
}else {
p2 = p2.next;
}
}
return p2;
}
