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

一、引子

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

二、題目

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

1、思路

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

兩條相交的鏈表呈Y型?？梢詮膬蓷l鏈表尾部同時(shí)出發(fā)，最后一個(gè)相同的結(jié)點(diǎn)就是鏈表的第一個(gè)相同的結(jié)點(diǎn)。可以利用棧來(lái)實(shí)現(xiàn)。時(shí)間復(fù)雜度有O(m + n), 空間復(fù)雜度為O(m + n)

2、編程實(shí)現(xiàn)

python

代碼實(shí)現(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
        
        #定義一個(gè)新的棧倒敘存放兩個(gè)節(jié)點(diǎn)
        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ù)，樂享生活：我們的公眾號(hào)計(jì)算機(jī)視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！

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

審核編輯 黃昊宇