朴素解法

一个朴素的解法自然是两层枚举，逐个检查哪个节点相同。

代码：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode a, ListNode b) {
        for (ListNode h1 = a; h1 != null ; h1 = h1.next) {
            for (ListNode h2 = b; h2 != null ; h2 = h2.next) {
                if (h1 == h2) return h1;
            }
        }
        return 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;
    }
}
  • 时间复杂度：
  • 空间复杂度：

Set 解法

这是一种「从前往后」找的方式。

使用 Set 数据结构，先对某一条链表进行遍历，同时记录下来所有的节点。

然后在对第二链条进行遍历时，检查当前节点是否在 Set 中出现过，第一个在 Set 出现过的节点即是交点。

代码：

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode a, ListNode b) {
        Set<ListNode> set = new HashSet<>();
        while (a != null) {
            set.add(a);
            a = a.next;
        }
        while (b != null && !set.contains(b)) b = b.next;
        return b;
    }
}
  • 时间复杂度：
  • 空间复杂度：

差值法

由于两条链表在相交节点后面的部分完全相同，因此我们可以先对两条链表进行遍历，分别得到两条链表的长度，并计算差值 d。

让长度较长的链表先走 d 步，然后两条链表同时走，第一个相同的节点即是节点。

代码：

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode a, ListNode b) {
        int c1 = 0, c2 = 0;
        ListNode ta = a, tb = b;
        while (ta != null && c1++ >= 0) ta = ta.next;
        while (tb != null && c2++ >= 0) tb = tb.next;
        int d = c1 - c2;
        if (d > 0) {
            while (d-- > 0) a = a.next;
        } else if (d < 0) {
            d = -d;
            while (d-- > 0) b = b.next;
        }
        while (a != b) {
            a = a.next;
            b = b.next;
        }
        return a;
    }
}
  • 时间复杂度：
  • 空间复杂度：

等值法

这是「差值法」的另外一种实现形式，原理同样利用「两条链表在相交节点后面的部分完全相同」。

我们令第一条链表相交节点之前的长度为 a，第二条链表相交节点之前的长度为 b，相交节点后的公共长度为 c（注意 c 可能为 ，即不存在相交节点）。

分别对两条链表进行遍历：

  • 当第一条链表遍历完，移动到第二条链表的头部进行遍历；
  • 当第二条链表遍历完，移动到第一条链表的头部进行遍历。

如果存在交点：**第一条链表首次到达「第一个相交节点」的充要条件是第一条链表走了 步，由于两条链表同时出发，并且步长相等，因此当第一条链表走了 步时，第二条链表同样也是走了 步，即 第二条同样停在「第一个相交节点」的位置。**

如果不存在交点：**两者会在走完 之后同时变为 ，退出循环。**

代码：

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode a, ListNode b) {
        ListNode ta = a, tb = b;
        while (ta != tb) {
            ta = ta == null ? b : ta.next;
            tb = tb == null ? a : tb.next;
        }
        return ta;
    }
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「剑指 の 精选」系列文章的第 No.36 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)