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

一、引子

這個系列是我在牛客網上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。

二、題目

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

1、思路

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

兩條相交的鏈表呈Y型。可以從兩條鏈表尾部同時出發，最后一個相同的結點就是鏈表的第一個相同的結點。可以利用棧來實現。時間復雜度有O(m + n), 空間復雜度為O(m + n)

2、編程實現

python

代碼實現方案：

# -*- 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
        
        #定義一個新的棧倒敘存放兩個節點
        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

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

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇