两个链表的第一个公共结点

两个链表的第一个公共结点_牛客题霸_牛客网

问题简述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

思路1：计算长度差

• 计算两个链表的长度差 d；让长的链表先走 d 步；

Python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        def get_len(cur):
            cnt = 0
            while cur:
                cnt += 1
                cur = cur.next
            return cnt
        
        l1 = get_len(pHead1)
        l2 = get_len(pHead2)
        
        if l1 < l2:
            return self.FindFirstCommonNode(pHead2, pHead1)
        
        cur1, cur2 = pHead1, pHead2
        
        d = l1 - l2
        while d:
            cur1 = cur1.next
            d -= 1
        
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        
        return cur1

思路2：拼接两个链表

Python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        c1, c2 = pHead1, pHead2
        while c1 != c2:
            c1 = c1.next if c1 else pHead2
            c2 = c2.next if c2 else pHead1
        
        return c1