当前位置：网站首页>牛客每日刷题之链表

牛客每日刷题之链表

2022-08-09 05:38:00 【_18shou】

作者简介：我是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;
    }
}