题解 | #反转链表#

这道题想了46分钟，依次想到的思路如下： （1）暴力遍历所有可能性，就是两个for循环 （2）采用Hash表的方法，这种方式的空间复杂度应该是o(n) （3）双指针，没想明白怎么弄来着 （4）想到了一种基于序列长度的方法：将两个序列的尾部对齐，从左到右对齐的部分依次比较

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

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
import sys
import math
sys.setrecursionlimit(100000)

class Solution:

    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        pHead1Length = 0
        pHead2Length = 0
        pHead1Shadow = pHead1
        pHead2Shadow = pHead2
        while pHead1Shadow:
            pHead1Shadow = pHead1Shadow.next
            pHead1Length += 1
        while pHead2Shadow:
            pHead2Shadow = pHead2Shadow.next
            pHead2Length += 1
        commonLength = pHead1Length if pHead1Length < pHead2Length else pHead2Length
        delta1 = pHead1Length - commonLength
        delta2 = pHead2Length - commonLength
        while pHead1 and delta1 > 0:
            pHead1 = pHead1.next
            delta1 -= 1
        while pHead2 and delta2 > 0:
            pHead2 = pHead2.next
            delta2 -= 1
        while pHead1 and pHead2:
            if pHead1.val == pHead2.val:
                return pHead1
            pHead1 = pHead1.next 
            pHead2 = pHead2.next 
        return None