题解 | #两个链表的第一个公共结点01#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while(l1 != l2){
l1 = (l1==null)?pHead2:l1.next;
l2 = (l2==null)?pHead1:l2.next;
}
return l1;
}
}
双指针：
让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。
因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。
所以，如何得到公共节点：
- 有公共节点的时候，N1和N2必会相遇，因为长度一样嘛，速度也一定，必会走到相同的地方的，所以当两者相等的时候，则会第一个公共的节点
- 无公共节点的时候，此时N1和N2则都会走到终点，那么他们此时都是null，所以也算是相等了。
阿里云工作强度 731人发布
投递哔哩哔哩等公司6个岗位