2019-08-08 剑指 两个链表的第一个公共结点

3min。投机取巧的办法

class Solution:
    def FindFirstCommonNode(self, pHead1:ListNode, pHead2:ListNode):
        tmp=set()
        while pHead1!=None:
            tmp.add(pHead1)
            pHead1=pHead1.next
        while pHead2!=None:
            if pHead2 in tmp:return pHead2
            pHead2=pHead2.next
        return None

使用栈来进行逆向
20min
1.result在何时进行初始化
2.公共节点是第一个的特殊情况

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        tmp1=[]
        tmp2=[]
        while pHead1!=None:
            tmp1.append(pHead1)
            pHead1=pHead1.next
        while pHead2!=None:
            tmp2.append(pHead2)
            pHead2=pHead2.next
        result = None
        while tmp1 and tmp2:
            #result=None #这里的错误
            if tmp1[-1]==tmp2[-1]:
                result=tmp1[-1]
                tmp1.pop()
                tmp2.pop()
            else:return result
        return result #公共节点为首位的特殊情况这里要考虑

精简版本

        tmp1=[]
        tmp2=[]
        while pHead1!=None:
            tmp1.append(pHead1)
            pHead1=pHead1.next
        while pHead2!=None:
            tmp2.append(pHead2)
            pHead2=pHead2.next
        result = None
        while tmp1 and tmp2 and tmp1[-1]==tmp2[-1]:
            result=tmp1[-1]
            tmp1.pop()
            tmp2.pop()
        return result

10min，采用计数，没有使用额外空间的方法。从栈的方法演化而来。心里过一遍边界条件。

        cnt1=0
        cnt2=0
        cur=pHead1
        while cur!=None:
            cnt1+=1
            cur=cur.next
        cur=pHead2
        while cur!=None:
            cnt2+=1
            cur=cur.next
        
        tmp=abs(cnt1-cnt2)  #表示相差的节点个数
        while tmp!=0:
            if cnt1 >= cnt2:
                pHead1=pHead1.next
            else:
                pHead2=pHead2.next
            tmp-=1
        while pHead1 and pHead1!=pHead2:  #要考虑到结尾的时候怎么处理
            pHead1=pHead1.next
            pHead2=pHead2.next
        return pHead1