【Leetcode】160. Intersection of Two Linked Lists

求两个链表的交点

方法1 长度差法

首先求出长的链表比短的链表长了多少（比如长了m），然后从长链表先走m步，然后两个链表一起走，即可相遇

class Solution1(object):
    def getIntersectionNode(self,headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        l1,l2 = headA,headB
        while(l1 and l2):
            l1 = l1.next
            l2 = l2.next
        if l2:
            l1,l2 = l2,l1
            headA,headB = headB,headA
        while(l1):
            headA =headA.next
            l1 = l1.next
        while(headA!=headB):
            headA = headA.next
            headB = headB.next
        return headA

方法2

discuss 大神方法

如果从A出发的点从走完a1-c3,再走完b1-b3，从B出发的点先走完b1-c3再走完a1-a2,那么他们肯定会相遇在c1。就算没有交点，最终也会在等于None出相等。利用总路程相等的思想，我们可以写出下面的代码

class Solution2(object):
    def getIntersectionNode(self,headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        l1,l2 = headA,headB
        while(l1 != l2):
            l1 = l1.next if l1 != None else headB
            l2 = l2.next if l2 != None else headA
        return l1