每日算法题 | 剑指offer 链表专题 （10） 两个链表的第一个公共结点
2021-03-10 20:27
标签：最大和 lis 复制 offer 二叉树的镜像 左旋转字符串 mic 逆序对 指针 两个链表的第一个公共结点 输入两个链表，找出它们的第一个公共结点。 思路二： 后记 如果是单纯的面试需求，剑指offer的优先级肯定是在Leetcode之前，总的说它有三个优点： 它的缺点是： 剑指offer刷题交流群 扫码添加微信，一定要备注研究方向+地点+学校+昵称（如机器学习+上海+上交+汤姆），只有备注正确才可以加群噢。 每日算法题 | 剑指offer 链表专题 （10） 两个链表的第一个公共结点 标签：最大和 lis 复制 offer 二叉树的镜像 左旋转字符串 mic 逆序对 指针 原文地址：https://blog.51cto.com/15054042/2564459
题目
题目要求
解题思路
思路一：两条相交的链表呈Y型。可以从两条链表尾部同时出发，最后一个相同的结点就是链表的第一个相同的结点。可以利用栈来实现。时间复杂度有O(m + n), 空间复杂度为O(m + n)
思路一其实利用栈主要解决就是同时到达第一个结点的问题，需要有额外的空间。那么从链表头出发如何同时到达第一个相同的结点呢? 链表的长度相同就可以，其实就是走的结点数目相同。所以可以让其中长的链表先走几步，走多少步呢？走M-N步。（M>N,M为链表1长度，N为链表2长度）剩余的长度到短链表的长度相同。Python :
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, head1, head2):
if not head1 or not head2:
return None
p1, p2= head1, head2
length1 = length2 = 0
while p1:
length1 += 1
p1 = p1.next
while p2:
length2 += 1
p2 = p2.next
if length1 > length2:
while length1 - length2:
head1 = head1.next
length1 -= 1
else:
while length2 - length1:
head2 = head2.next
length2 -= 1
while head1 and head2:
if head1 is head2:
return head1
head1 = head1.next
head2 = head2.next
return NoneJAVA
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==NULL||pHead2==NULL)return NULL;
//首先遍历两个链表获取长度
ListNode *pNode1=pHead1,*pNode2=pHead2;
int listLength1=0,listLength2=0;
while(pNode1!=NULL){
++listLength1;
pNode1=pNode1->next;
}
while(pNode2!=NULL){
++listLength2;
pNode2=pNode2->next;
}
//比较长度，长的先走dist步
pNode1=pHead1;
pNode2=pHead2;
if(listLength1>listLength2){
for(int i=0;i
注：面试季来了，不管是作为面试者还是以后作为面试官，了解算法这门程序员之间的沟通方式都是非常必要的。找过工作的朋友应该都听说过《剑指offer》，虽然书中只有六十多道题目，但是道道都是经典。
算法题主要分成数据结构和具体算法部分，简单归类如下。基本每道题都很精彩，所以这里就不一一洗写了，题解可以看看我的代码仓库或者讨论区的内容。数据结构类题目
▲长按加群
下一篇：N皇后问题 -Python
文章标题：每日算法题 | 剑指offer 链表专题 （10） 两个链表的第一个公共结点
文章链接：http://soscw.com/index.php/essay/62909.html