Q160 Intersection of Two Linked Lists

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        A = A1 = headA; B = B1 = headB
        lenA = lenB = 0
        # 计算链表 A,B 的长度
        while A != None:
            lenA += 1
            A = A.next
        while B != None:
            lenB += 1
            B = B.next
        # 尾对齐链表
        if lenA > lenB:
            diff = lenA - lenB
            while diff > 0:
                A1 = A1.next
                diff -= 1
        else:
            diff = lenB - lenA
            while diff > 0:
                B1 = B1.next
                diff -= 1
        # 从对应的位置开始比较
        while A1 != None and B1 != None and A1.val != B1.val:
            A1 = A1.next
            B1 = B1.next
        return A1  # 或者返回B1