问题: 输入两个链表,找出它们的第一个公共节点。
如下面的两个链表:
分析:
该问题分为两种情况
情况1. 存在公共节点 如果A的长度是l1+C, B的长度是l2+C。C为公共部分长度。A B长度不一样的话,首先要考虑互补彼此。因为两个指针需要一起走,所以互补的最基本方式就是公共都走(l1+l2)长度的节点,遍历到链表尾还得加C 所以是(l1+l2+C)个长度。
情况2. 不存在公共点 headA headB分别遍历过彼此 最后None=None 退出循环 返回None这样,当他们相遇,所指的结点就是第一个公共节点。
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pA = headA
pB = headB
while pA != pB:
pA = pA.next if pA != None else headB
pB = pB.next if pB != None else headA
return pA