Intersection of Two Linked Lists

首先是CC189里面讲的方法，比较暴力，先遍历一遍数一下两个链的长度是多少，这时候如果到了最末尾两个结点还不相等那就是没交点了，接下来通过长度判断哪边长一些，长一些的点先移到长度两边相等的位置，再继续往前推进找交点就行

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lengthOfA, lengthOfB = 0, 0
        aPointer, bPointer = headA, headB
        while aPointer or bPointer:
            if aPointer:
                lengthOfA += 1
                aPointer = aPointer.next
            if bPointer:
                lengthOfB += 1
                bPointer = bPointer.next

        if aPointer != bPointer:
            return None

        aPointer, bPointer = headA, headB
        if lengthOfA > lengthOfB:
            step = lengthOfA - lengthOfB
            while step:
                aPointer = aPointer.next
                step -= 1
        else:
            step = lengthOfB - lengthOfA
            while step:
                bPointer = bPointer.next
                step -= 1

        while aPointer and bPointer and aPointer != bPointer:
            aPointer = aPointer.next
            bPointer = bPointer.next

        return aPointer

这道题还有一个更加叼的办法，首先明确一点，不管a链和b链是否相交，如果两个指针在两条链上都遍历一遍则我们根本不需要担心长度差的问题，所以我们可以用一个指针pA先遍历a链，如果a链遍历完了就把pA指向b链，pB指针也一样，这样我们最后找到的两个指针的共同结点就是两条链的交点，如果没交点，则pA和pB相等的位置肯定就是空节点的位置了

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pA, pB = headA, headB
        while pA != pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA