【剑指offer】两个链表的第一个公共节点 python/Java

【题目描述】

输入两个链表，找出它们的第一个公共结点。

【思路】

思路1:计算两个链表的长度，计算出长度差，令较长的链表先走完长度差步数，然后二者开始一起遍历，直到遇到第一个相同节点。

思路2:无需遍历两个链表，无需计算长度；两个链表均从头开始遍历，当一个链表遍历到链表尾部，该节点就更新为另一个链表的第一个节点。相当于判断谁先走到了头，先走到头的回来继续走，相当于减去长链表比短链表长的部分，然后2个相同长度的链表从头开始遍历。此方法更优。

【代码】

python：
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        p1,p2=pHead1, pHead2
        while(p1!=p2):
            if p1:
                p1=p1.next
            else:
                p1=pHead2
            if p2:
                p2=p2.next
            else:
                p2=pHead1
        return p1

java:
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
   ListNode p1=pHead1;
   ListNode p2=pHead2;
   while(p1!=p2){
       if(p1!=null){
           p1=p1.next;
       }else{
           p1=pHead2;
       }
       if(p2!=null){
           p2=p2.next;
       }else{
           p2=pHead1;
       }
   }
        return p1;
        
    }
}