02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
思路
两个链表长度可能不一样,我们一般是想让链表从同一起点索引开始比较,防止遗漏,所以先求各自长度,然后让长的链表先移动长度差个单位。
要注意,交点不是数值相等,而是指针相等。
另外,注意没找到返回空指针。
class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""lista = headAlistb = headB# 先分别计算出 链表A 和 链表B 的长度sizea, sizeb = 0, 0while lista:lista = lista.nextsizea += 1while listb:listb = listb.nextsizeb += 1d = abs(sizea - sizeb) # 链表A和链表B长度差lista = headAlistb = headB# A比B长 那么A先走d步if sizea > sizeb: for i in range(d):lista = lista.nextelse: # B比A长 那么B先走d步for i in range(d):listb = listb.next# 现在两个起点一样while lista: # 判断是否到Noneif lista == listb:return listaelse:lista = lista.nextlistb = listb.nextreturn None # 注意返回空指针