【算法与数据结构相关】【LeetCode】【160 相交链表】【Python】_找出两个链表相交的结点(定义链表结构) python实现

题目：编写一个程序，找到两个单链表相交的起始节点。例如，下面的两个链表在节点 c1 开始相交。

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

思路：

1. 将链表A反转，那么如果两个链表相交，则从b1开始遍历最终会到达a1点，所以通过判断b1遍历到最后是否与a1相同即可，关于相交位置可以这么计算，遍历A得其长度M，遍历B得其长度N，遍历b1至a1得其长度Q。a1至c1长度为x，b1至c1长度为y，c1至c3长度为z，则可得到三个等式求出x，y，z。
2. 分别遍历两个链表，如果尾节点不同则不相交，返回None，如果尾节点相同则求相交结点。 求相交结点的方法是，求出链表长度的差值，长链表的指针先想后移动lenA-lenB。然后两个链表一起往后走，若结点相同则第一个相交点。 
3. 先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？ 

代码： 

# 思路2
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lenA, lenB = 0, 0
        pA = headA
        pB = headB
        while pA:
            pA = pA.next
            lenA += 1
        while pB:
            pB = pB.next
            lenB += 1
        pA = headA
        pB = headB
        if lenA > lenB:
            for i in range(lenA-lenB):
                pA = pA.next
        else:
            for i in range(lenB-lenA):
                pB = pB.next
        while pA!=pB:
            pA = pA.next
            pB = pB.next
        return pA

但是！！！有大神给出了极为简洁的解法，其思路是这样的：分别将两个列表连接到对方链表的末尾，则得到的两个链表长度是相同的，若原两个链表相交，则在从头遍历两个新链表时一定会存在一个位置相同（这么说有点抽象，自己画一下就知道了）

上代码！

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