两个链表的第一个公共节点---遍历彼此的节点

问题: 输入两个链表,找出它们的第一个公共节点。

如下面的两个链表:
两个链表的第一个公共节点---遍历彼此的节点

分析:

该问题分为两种情况

情况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
上一篇:洛谷P3073题解


下一篇:指针常量&常量指针