假设链表一走到相同节点的距离为a,链表二为b,从相同节点到末尾的距离为c;
我们可以让两个链表走相同的路,若走到相同节点,就返回。
算法核心: a+b+c = b+c+c
就算它们走完都没有相同节点,也不碍事,返回的都是null也是相等的。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2){
p1 = (p1 == null ? pHead2 : p1.next);
p2 = (p2 == null ? pHead1 : p2.next);
}
return p1;
}
京公网安备 11010502036488号