题解 | #两个链表的第一个公共结点#

一、python3链表结构

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

二、输入、输出

输入：两个链表的头结点的指针（将这两个链表看成是完整链表，也就是按题中描述组装之后的链表）

输出：第一个共同结点的指针

@param pHead1 ListNode类 
@param pHead2 ListNode类 
@return ListNode类

三、解题思路

1. 在while pTmp1 and pTmp2:中，需要注意当两链表长度相等的时候 它们会同时为None, 此时，下面两个if的判断都进不去，所以要在该循环之前加入两个链表对应结点相等的判断，当此时遇到一个相等结点，这个相等的结点直接就是要返回的两链表第一个相等的结点。
2. 算法过程：

①先从头至尾同时遍历两链表，每次同时推进一个指针。若长度相等，则直接遍历到相等的元素后就返回；若长度不等，则在同时往后推进遍历的过程中，短的链表先遍历完，此时短链表的指针指向None，长链表的指针指向下一个元素。

②在新一个while循环中，继续遍历没有遍历完的长链表，并且，每次往后推进一个，则k+=1，这样，当遍历长链表的指针指向None的时候，计数停止，计数数量等于长链表比短链表长的长度。（之后让长链表根据该数值先推进遍历，然后再与短链表一起遍历。）

③重置长链表与短链表的指针 指向他们本身开始的结点。让长链表先往后遍历k个结点，再让长短链表一起往后推进遍历，并在遍历过程中 比较长短链表当前指针指向的结点的值，当发现值相等时，则说明遍历到了第一个公共结点。（②③两过程只有当两链表长度不相等的时候才会发生，因为当两链表长度相等时，元素的遍历和比较已经在①中完成并返回）

3. 要注意将后两个if判断中大量相似的代码提取出来，写成find_equal函数，封装。 书写代码过程如下，先写繁琐的形式，然后从繁琐重复的形式中进行提炼封装。

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        def find_equal(shortPointer,longPointer,shortHead,longHead):
            k=0
            while longPointer:
                longPointer=longPointer.next
                k+=1
            shortPointer=shortHead
            longPointer=longHead
            for i in range(k):
                longPointer=longPointer.next
            while longPointer!=shortPointer:
                shortPointer=shortPointer.next
                longPointer=longPointer.next
            return shortPointer
        
  
        pTmp1=pHead1
        pTmp2=pHead2
        
        while pTmp1 and pTmp2:
            if pTmp1==pTmp2: # 当两链表一样长时，在相等处 同时变None
                return pTmp1
            pTmp1=pTmp1.next
            pTmp2=pTmp2.next
        
        if pTmp1:
            return find_equal(pTmp2,pTmp1,pHead2,pHead1)
        '''
            k=0
            while pTmp1:
                pTmp1=pTmp1.next
                k+=1
            pTmp1=pHead1
            pTmp2=pHead2
            for i in range(k):
                pTmp1=pTmp1.next
            while pTmp1!=pTmp2:
                pTmp1=pTmp1.next
                pTmp2=pTmp2.next
            return pTmp1
        '''
        if pTmp2:
            return find_equal(pTmp1,pTmp2,pHead1,pHead2)
        '''
            k=0
            while pTmp2:
                pTmp2=pTmp2.next
                k+=1
            pTmp1=pHead1
            pTmp2=pHead2
            for i in range(k):
                pTmp2=pTmp2.next
            while pTmp1!=pTmp2:
                pTmp1=pTmp1.next
                pTmp2=pTmp2.next
            return pTmp1
        '''

封装后简洁版本：（删去了写在注释中的过程代码，直接用封装的函数形式体现）

class Solution:
  def FindFirstCommonNode(self , pHead1 , pHead2 ):
      # write code here
      def find_equal(shortPointer,longPointer,shortHead,longHead):
          k=0
          while longPointer:
              longPointer=longPointer.next
              k+=1
          shortPointer=shortHead
          longPointer=longHead
          for i in range(k):
              longPointer=longPointer.next
          while longPointer!=shortPointer:
              shortPointer=shortPointer.next
              longPointer=longPointer.next
          return shortPointer
      

      pTmp1=pHead1
      pTmp2=pHead2
      
      while pTmp1 and pTmp2:
          if pTmp1==pTmp2: # 当两链表一样长时，在相等处 同时变None
              return pTmp1
          pTmp1=pTmp1.next
          pTmp2=pTmp2.next
      
      if pTmp1:
          return find_equal(pTmp2,pTmp1,pHead2,pHead1)
      if pTmp2:
          return find_equal(pTmp1,pTmp2,pHead1,pHead2)