[数据结构与算法]C/C++编程刷题分享—二维数组中的查找

?作者简介：嵌入式领域新星创作者，博客专家
?个人主页：咸鱼弟
🔥系列专栏：剑指offer专栏
📃推荐一款求职面试、刷题神器👉注册免费刷题

本次和大家一起分享的题目选自牛客网中的经典好题。那么今天带来一道简单题，用到的知识一目了然，思路清晰。刷题入口放在文章开头了，那么快来跟我一起刷题练习吧！

目录

1.题目描述

2.解题思路

3.参考代码

4.复杂度分析

?牛客网界面：

?

?

剑指offer题目专栏界面：?

?

?

1.题目描述

2.解题思路

解题思路：

使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。

让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。

因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。

（N1最后肯定能到达链表2的终点，N2肯定能到达链表1的终点）。

所以，如何得到公共节点：

• 有公共节点的时候，N1和N2必会相遇，因为长度一样嘛，速度也一定，必会走到相同的地方的，所以当两者相等的时候，则会第一个公共的节点
• 无公共节点的时候，此时N1和N2则都会走到终点，那么他们此时都是null，所以也算是相等了。

下面看个动态图，可以更形象的表示这个过程~

3.参考代码

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;
        }
        return l1;
    }

4.复杂度分析

时间复杂度：O(m+n)。链表1和链表2的长度之和。

空间复杂度：O(1)。常数的空间。