160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

解法一：差距法

先判断长链短链，并求出长度差diff

长链先走diff步，之后长短链一起走，若有交点，走到尽头之前必然同时会聚。

# 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
        """
        lenA, lenB = 0, 0
        pA, pB = headA, headB  #工作指针
        #测量两个链的长度
        while pA:
            lenA += 1
            pA = pA.next
        while pB:
            lenB += 1
            pB = pB.next
        #判断长链短链
        if lenA > lenB:
            longList = headA
            shortList = headB
        else:
            longList = headB
            shortList = headA
            
        diff = abs(lenA - lenB)  #长链和短链的差
        #长链先走相差的长度
        for _ in range(diff):
            longList = longList.next
        #然后两个链一起走    
        while longList and shortList:
            if longList == shortList:  #会聚，说明找到交点
                return longList
            longList = longList.next
            shortList = shortList.next