力扣刷题-链表-链表相交

02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

思路

两个链表长度可能不一样，我们一般是想让链表从同一起点索引开始比较，防止遗漏，所以先求各自长度，然后让长的链表先移动长度差个单位。
要注意，交点不是数值相等，而是指针相等。
另外，注意没找到返回空指针。

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
        """
        lista = headA
        listb = headB
        # 先分别计算出 链表A 和 链表B 的长度
        sizea, sizeb = 0, 0
        while lista:
            lista = lista.next
            sizea += 1
        while listb:
            listb = listb.next
            sizeb += 1
        d = abs(sizea - sizeb) # 链表A和链表B长度差
        lista = headA
        listb = headB
        # A比B长 那么A先走d步
        if sizea > sizeb: 
            for i in range(d):
                lista = lista.next
        else: # B比A长 那么B先走d步
            for i in range(d):
                listb = listb.next
        # 现在两个起点一样
        while lista: # 判断是否到None
            if lista == listb:
                return lista
            else:
                lista = lista.next
                listb = listb.next
        return None # 注意返回空指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39