[数据结构与算法]JZ36 两个链表的第一个公共结点

描述

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

?姚青林老师的思路是?①先一次循环找到两个链表长度之差k②让长链表先走k步，然后一起走，只要找到第一个公共结点。

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

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        pTmp1 = pHead1
        pTmp2 = pHead2
        while pTmp1 and pTmp2:
            if pTmp1 == pTmp2:
                return pTmp1
            pTmp1 = pTmp1.next
            pTmp2 = pTmp2.next
        #链表1比较长的情况    
        if pTmp1:
            k = 0
            #寻找出链表长度之间的差值
            while pTmp1:
                pTmp1 = pTmp1.next
                k += 1
            #先让长的那个链表走k步
            pTmp1 = pHead1
            pTmp2 = pHead2
            for i in range(k):
                pTmp1 = pTmp1.next
            while pTmp1 != pTmp2:
                pTmp1 = pTmp1.next
                pTmp2 = pTmp2.next
            return pTmp1
        #链表2比较长的情况        
        if pTmp2:
            k = 0
            #寻找出链表长度之间的差值
            while pTmp2:
                pTmp2 = pTmp2.next
                k += 1
            #先让长的那个链表走k步
            pTmp1 = pHead1
            pTmp2 = pHead2
            for i in range(k):
                pTmp2 = pTmp2.next
            while pTmp1 != pTmp2:
                pTmp1 = pTmp1.next
                pTmp2 = pTmp2.next
            return pTmp2
                

可以继续简化代码，封装一下函数：

#第一个参数给比较短的那个链表
#第二个参数给比较长的那个链表
#第三个参数给比较短的那个链表头
#第二个参数给比较长的那个链表头
def findequal(shortPointer, longPointer, shortHead, longHead):
    k = 0
    #寻找出链表长度之间的差值
    while longPointer:
        longPointer = longPointer.next
        k += 1
    #先让长的那个链表走k步
    shortPointer = shortHead
    longPointer = longHead
    for i in range(k):
        longPointer = longPointer.next
    while shortPointer != longPointer:
        shortPointer = shortPointer.next
        longPointer = longPointer.next
    return shortPointer 

?那上面的代码可以变成：

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

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        #第一个参数给比较短的那个链表
        #第二个参数给比较长的那个链表
        #第三个参数给比较短的那个链表头
        #第二个参数给比较长的那个链表头
        def findequal(shortPointer, longPointer, shortHead, longHead):
            k = 0
            #寻找出链表长度之间的差值
            while longPointer:
                longPointer = longPointer.next
                k += 1
            #先让长的那个链表走k步
            shortPointer = shortHead
            longPointer = longHead
            for i in range(k):
                longPointer = longPointer.next
            while shortPointer != longPointer:
                shortPointer = shortPointer.next
                longPointer = longPointer.next
            return shortPointer 

        # write code here
        pTmp1 = pHead1
        pTmp2 = pHead2
        while pTmp1 and pTmp2:
            if pTmp1 == pTmp2:
                return pTmp1
            pTmp1 = pTmp1.next
            pTmp2 = pTmp2.next
        #链表1比较长的情况    
        if pTmp1:
           return findequal(pTmp2, pTmp1, pHead2, pHead1)
        #链表2比较长的情况        
        if pTmp2:
           return findequal(pTmp1, pTmp2, pHead1, pHead2)
       

?