剑指Offer(三十六):两个链表的第一个公共结点

  • A+
所属分类:剑指Offer
摘要

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

剑指Offer(三十六):两个链表的第一个公共结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

这道题和160.Intersection of Two Linked Lists是一样的。都是求两个链表的第一个公共结点。

公共结点的样子:

剑指Offer(三十六):两个链表的第一个公共结点

上图就是一个有公共结点的例子,在公共结点之后,两个链表指针指向的地址是相同的。

这道题有两个解法。

方法一:

我们可以把两个链表拼接起来,一个pHead1在前pHead2在后,一个pHead2在前pHead1在后。这样,生成了两个相同长度的链表,那么我们只要同时遍历这两个表,就一定能找到公共结点。时间复杂度O(m+n),空间复杂度O(m+n)。

方法二:

我们也可以先让把长的链表的头砍掉,让两个链表长度相同,这样,同时遍历也能找到公共结点。此时,时间复杂度O(m+n),空间复杂度为O(MAX(m,n))。

2、代码

C++:

这里使用方法二。

Python:

这里使用方法一:

Jack Cui
阿里云ECS

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: