《剑指offer》--- 两个链表的第一个公共结点

本文算法使用python3实现


1. 问题

  输入两个链表,找出它们的第一个公共结点。
  时间限制:1s;空间限制:32768K


2 思路描述

  使用两个指针 $ p1,p2 $ 分别指向两个链表的第一个节点 $ pHead1, pHead2 $ 。将分为以下几种情况:
  (1)当两个链表长度相等,且有公共节点时,两个指针同时后移,会找到第一个公共节点。当 $ p1=p2 $ 时退出。


1238724-20180621114225951-1802321698.jpg

  (2)当两个链表长度相等,且没有公共节点时,两个指针同时后移,直到两个指针都指向 None 退出。


1238724-20180621114531787-499070740.jpg

  (3)当两个链表长度不等,且有公共节点时,两个指针同时后移,当 $ p1 $ 指向 None 后,将其重新指向第二个链表的第一个节点 $ p1=pHead2 $ 。当 $ p2 $ 指向 None 后,将其重新指向第一个链表的第一个节点 $ p2=pHead1 $ 。当 $ p1=p2 $ 时退出。


1238724-20180621115225778-1494686541.jpg

  (4)当两个链表长度不等,且没有公共节点时,两个指针同时后移,当 $ p1 $ 指向 None 后,将其重新指向第二个链表的第一个节点 $ p1=pHead2 $ 。当 $ p2 $ 指向 None 后,将其重新指向第一个链表的第一个节点 $ p2=pHead1 $ 。当 $ p1=p2=None $ 时退出。


1238724-20180621115539921-1101583183.jpg

3 程序代码:

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        if not pHead1 or not pHead2:  
            return None  
        p1, p2 = pHead1, pHead2  
        while p1 != p2:  
            p1 = pHead2 if not p1 else p1.next  
            p2 = pHead1 if not p2 else p2.next  
        return p1 

原文链接:加载失败,请重新获取