假设链表一走到相同节点的距离为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; }