Sword to Offer-52 两个链表的第一个公共结点 ❀

08 May 2020 in Algorithm

• 题目描述：
  输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路：

假设链表1：a+c，链表2：b+c
1、若a==b，直接能找到第一个相同点；
2、若a！=b，假设a<b，pa到达终点时，pb离终点b-a，pa到终点后从链表2起点开始往后走， pb到达终点时，pa已经在链表2走了b-a，之后pb从链表1起点开始走， 当pb走了a到达交点时，pa走了b-a+a=b也到达了交点。

同类型的题为23。

问题图解：

AC代码：

// The First Common Node of Two LinkedList

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode pNode1 = pHead1;
        ListNode pNode2 = pHead2;
        while (pNode1 != pNode2) {
            pNode1 = (pNode1==null) ? pHead2 : pNode1.next;
            pNode2 = (pNode2==null) ? pHead1 : pNode2.next;
        }
        return pNode1;
    }
}

补充说明：

• 这里是牛客编码链接