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

直接使用蛮力法，先遍历第一个链表，然后遍历第二个，判断是不是同一个结点，是的话返回就行，但是这样时间复杂度O(m*n)。

改进一步可以先得到两个链表的长度la和lb，假设la>lb（反过来当然一样），然后la先走la-lb步，然后双指针同步走，相同的第一个元素就是公共节点，返回即可。

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
        cur1 = pHead1
        while cur1:
            cur2 = pHead2
            while cur2:
                if cur1 == cur2:
                    return cur1
                else:
                    cur2 = cur2.next
            cur1 = cur1.next
        return None


pHead1 = ListNode(1)
pHead1.next = ListNode(2)
pHead2 = ListNode(3)
pHead2.next = pHead1.next
x = Solution().FindFirstCommonNode(pHead1 , pHead2)
cur = x
while cur:
    print(cur.val)
    cur = cur.next