剑指offer-52两个链表的第一个公共结点-python

《剑指offer》python实现系列，全目录

题目描述：

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

第一想法:

a->b->c->d , h->b->c->d , 那么b是公共结点?

#暴力法 O(mn)
for i in listA:
    for j in listB:
        if i == j and i.next ==j.next:
            return

剑指offer方法一：

有公共结点，因为是单链表，只有一个next，说明尾部是相同的。

可以从尾部开始往前比较。那么最后一个相同的结点就是第一个公共结点。

但单链表只能从前往后比较，先进后出

建立两个长度为m和n的辅助栈，mn分别是两个链表的长度。

剑指offer方法二：

不需要辅助空间

首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。

在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None
        length1,length2=0,0
        cur1,cur2 = pHead1,pHead2
        #计算两个链表的长度
        while cur1 is not None: 
            length1 += 1
            cur1 = cur1.next
        while cur2 is not None:
            length2 += 1
            cur2 = cur2.next  
        
        #让长的链表先走
        cur1,cur2 = pHead1,pHead2
        if length2 > length1:
            for i in range(length2-length1):
                cur2 = cur.next
        elif length1 > length2:
            for i in range(length1-length2):
                cur1 = cur1.next
                
        while cur1 is not None:
            if cur1 == cur2:
                return cur1
            cur1 = cur1.next
            cur2 = cur2.next
        return None

一次AC,好久没有过的感觉了