【剑指offer】37. 两个链表的第一个公共节点(python)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【剑指offer】37. 两个链表的第一个公共节点(python)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1507字，纯文字阅读大概需要3分钟。

内容图文

题目描述

输入两个链表，找出它们的第一个公共结点。

思路

《剑指offer》P193

• 方法一
  使用辅助空间栈，遍历两个链表，将节点保存到栈中。然后利用栈先进后出的特点找到公共节点。
• 方法二
  先遍历一遍得到两个链表的长度m和n，假设m>n，则较长的链表先走m-n步，然后两个链表同时向后走，直到找到第一个公共节点。

code

• 方法一

# -*- 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
        while 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
        commonNode = None
        while stack2 and stack1:
            node1 = stack1.pop()
            node2 = stack2.pop()
            if node1 != node2:
                break
            else:
                commonNode = node1
        return commonNode

• 方法二

# -*- 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
        while not pHead1 or not pHead2:
            return None
        len1 = 0
        len2 = 0
        pNode1 = pHead1
        pNode2 = pHead2
        # 先计算长度
        while pNode1:
            len1 += 1
            pNode1 = pNode1.next
        while pNode2:
            len2 += 1
            pNode2 = pNode2.next
        # 较长的链表先移动
        while len1 > len2:
            pHead1 = pHead1.next
            len1 -= 1
        while len2 > len1:
            pHead2 = pHead2.next
            len2 -= 1
        # 两个链表同时移动
        while pHead2 and pHead1:
            if pHead2 == pHead1:
                break
            else:
                pHead2 = pHead2.next
                pHead1 = pHead1.next
        return pHead2

内容总结

以上是互联网集市为您收集整理的【剑指offer】37. 两个链表的第一个公共节点(python)全部内容，希望文章能够帮你解决【剑指offer】37. 两个链表的第一个公共节点(python)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端