劍指Offer（三十六）：兩個鏈表的第一個公共結點
搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners
一、引子
這個系列是我在牛客網上刷《劍指Offer》的刷題筆記，旨在提升下自己的演算法能力，
查看完整的劍指Offer演算法題決議請點擊CSDN和github鏈接：
劍指Offer完整習題決議CSDN地址
github地址
二、題目
輸入兩個鏈表，找出它們的第一個公共結點，
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
AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料
分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/72033.html
標籤：其他
上一篇：NVIDIA顯卡電源不足