[数据结构与算法] 牛客每日刷题之链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 牛客每日刷题之链表 -> 正文阅读

[数据结构与算法]牛客每日刷题之链表

?作者简介：我是18shou，一名即将秋招的java实习生

?个人主页：_18shou

🔥系列专栏：牛客刷题专栏

📃推荐一款模拟面试、刷题神器👉?在线刷题面经模拟面试

描述

输入两个无环的单向链表，找出它们的第一个公共结点, 如果没有公共节则返回空。(注意因为传入数据是链表, 所以错误测试数据的提示是用
其他方式显示的，保证传入数据是正确的)
数据范围: n < 1000
要求:空间复杂度0(1),时间复杂度0(n)

解析

使用两个指针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,所以也算是相等了。

代码
?

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode a, ListNode b) {
        Deque<ListNode> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        while (a != null) {
            d1.add(a);
            a = a.next;
        }
        while (b != null) {
            d2.add(b);
            b = b.next;
        }
        ListNode ans = null;
        while (!d1.isEmpty() && !d2.isEmpty() && d1.peekLast() == d2.peekLast()) {
            ans = d1.pollLast();
            d2.pollLast();
        }
        return ans;
    }
}