LintCode:2つのチェーンテーブルの交差

LintCode:2つのチェーンテーブルの交差
最も考えやすいのは、もちろんバブルアルゴリズムに似ています.コード:

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    # @param headA: the first list
    # @param headB: the second list
    # @return: a ListNode
    def getIntersectionNode(self, headA, headB):
        # Write your code here
        if headA == None or headB == None:
            return None
        p1 = headA
        p2 = headB
        while p1.next != None:
            while p2.next != None:
                if p1 == p2:
                    return p1
                p2 = p2.next
            p2 = headB
            p1 = p1.next
        return None

でも意外に...タイムアウトしました.
もう1つの態様では、長いチェーンテーブルを見つけてから、|len(A)−len(B)|の距離を後方に移動することで、2つのチェーンテーブルが同じ長さを有するようになり、バブル比較を行う必要がなくなり、複雑度もnに低下する.

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    # @param headA: the first list
    # @param headB: the second list
    # @return: a ListNode
    def getIntersectionNode(self, headA, headB):
        # Write your code here
        if headA == None or headB == None:
            return None
        p1 = headA
        p2 = headB
        len_a = 0
        len_b = 0
        while p1.next != None:
            len_a += 1
            p1 = p1.next
        while p2.next != None:
            len_b += 1
            p2 = p2.next
        len_c = abs(len_a - len_b)
        p1 = headA
        p2 = headB
        if len_a >= len_b:
            for i in range(len_c):
                p1 = p1.next
        else:
            for i in range(len_c):
                p2 = p2.next
        while p1 != None and p2 != None:
            if p1 == p2:
                return p1
            p1 = p1.next
            p2 = p2.next
        return None