劍指Offer（36）：兩個鏈表的第一個公共結(jié)點

一、引子

這個系列是我在?？途W(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。

二、題目

輸入兩個鏈表，找出它們的第一個公共結(jié)點。

1、思路

如果存在共同節(jié)點的話，那么從該節(jié)點，兩個鏈表之后的元素都是相同的。也就是說兩個鏈表從尾部往前到某個點，節(jié)點都是一樣的。

兩條相交的鏈表呈Y型?？梢詮膬蓷l鏈表尾部同時出發(fā)，最后一個相同的結(jié)點就是鏈表的第一個相同的結(jié)點?？梢岳脳韺崿F(xiàn)。時間復雜度有O(m + n), 空間復雜度為O(m + n)

2、編程實現(xiàn)

python

代碼實現(xiàn)方案：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        
        #定義一個新的棧倒敘存放兩個節(jié)點
        stack1 = []
        stack2 = []
        
        while pHead1:
            stack1.append(pHead1)
            pHead1 = pHead1.next
            
        while pHead2:
            stack2.append(pHead2)
            pHead2 = pHead2.next
            
        first = None
        while stack1 and stack2:
            top1 = stack1.pop()
            top2 = stack2.pop()
            if top1 is top2:
                first=top1
            else:
                break
        return first

分享技術(shù)，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

審核編輯 黃昊宇