剑指Offer34 寻找链表相同节点

输入两个链表，找出它们的第一个公共结点。（公共节点是指节点的内存地址一样）

存在公共节点意味着公共节点后面的链表相同，此时链表的形状应是>----。需要注意的是

1. 如果链表的长度相同，好说，直接遍历一趟就找到了。
2. 如果链表的长度不同，我们就要先除去长出的那部分。

解决方法：

1. 暴力法，求解两个链表的长度，把长的那部分去除掉再去找公共节点，链表遍历了三遍。

---

2. 链表拼接：理解就是两个链表长度之和是一样的。
   比如说：
   链表A：3-4-5
   链表B：9-8-7-4-5
   第一个公共节点是4，我们把两个链表拼接起来：
   A+B = 3-4-5-9-8-7-4-5
   B+A = 9-8-7-4-5-3-4-5
   可以看到，在合并后的链表依然会出现公共节点，并且位置一样。
   当然实际操作并不需要拼接。

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;
}

如果链表的长度一样，一遍结束，否则遍历拼接部分。