组里新来的 00后，试用期工资8k，住家里没房贷, 昨天项目上线，全组人都在，6点01分他准时背着包走了。

面试题：相交链表

相交链表这个题啊，其实挺口水的一个题，但每次面试都爱考。 我前几天在公司楼下等外卖的时候，我们组那个小李还拿着手机问我：哥，这玩意到底考啥呀，看着就两条链表，绕来绕去脑袋疼。

我跟他说，你先别急着上来就写代码，先想象一个画面：两条路，一条从你家出发，一条从你对象家出发，最后汇合到公司门口，汇合之后走的那一段路是完全同一段，不是“看着差不多”，是 同一块水泥地。相交链表说的就是这个感觉，是同一个节点的引用相交，不是值一样就算。

相交链表到底想干嘛

题目大概意思就是：给你两个单链表 headA 和 headB，问这俩有没有相交，如果有，返回相交的那个节点；没有就返回 null。

有两个点，很多人一开始都会搞错：

1. 相交的意思是“节点地址一样”，也就是 nodeA == nodeB，不是 nodeA.val == nodeB.val
2. 从相交点开始，后面的所有节点都是共享的，所以形状长这样：Y 型，不存在 X 型那种你来我往

所以你千万别上来整一个“把链表 A 的值丢到 HashSet 里，再用 B 去查”的骚操作，那是错的，值可以重复，人家考的是“引用”。

最笨的办法，为什么不行

小李当时说，他第一反应就是两层循环：

• A 的每个节点
• 配上 B 的每个节点
• 有一个 a == b 就说明相交了

时间复杂度是多少？ 假设 A 长度 m，B 长度 n，那就是 O(m * n)，链表一长，直接超时警告。 面试官要是看你写这个，多半会顺手问一句：“有没有更快的？”——这就有戏了。

稍微聪明点的想法：先对齐再一起走

那怎么变快？其实思路特别生活化，我当时就是这么给小李比喻的。

你想象两个人去赶地铁：

• 甲在距离地铁口 100 米的地方
• 乙在距离地铁口 200 米的地方

你们要同时到达地铁口，怎么办？ 很简单嘛，让离得远的那个多走 100 米，走到和另一个人齐平，再一起往前走，就能同步到达终点。

放到链表里也是一样的：

1. 先算出两条链表的长度 lenA 和 lenB
2. 让长的那条链表先走 |lenA - lenB| 步
3. 然后两个指针一起一步一步往前，如果有 p == q 的地方，就是相交点；走到头还没相等，那就是没相交

逻辑挺顺的，写成 Java 也不难，直接上代码：

// 链表节点定义（和 LeetCode 那个一样）
classListNode{
int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

publicclassSolution{

public ListNode getIntersectionNode(ListNode headA, ListNode headB){
if (headA == null || headB == null) {
returnnull;
        }

// 1. 先求两条链表的长度
int lenA = 0, lenB = 0;
        ListNode p = headA, q = headB;

while (p != null) {
            lenA++;
            p = p.next;
        }
while (q != null) {
            lenB++;
            q = q.next;
        }

// 2. 让长的那条先走几步
        p = headA;
        q = headB;
if (lenA > lenB) {
int diff = lenA - lenB;
while (diff-- > 0) {
                p = p.next;
            }
        } else {
int diff = lenB - lenA;
while (diff-- > 0) {
                q = q.next;
            }
        }

// 3. 一起往前走，遇到相同节点就返回
while (p != null && q != null) {
if (p == q) {
return p;
            }
            p = p.next;
            q = q.next;
        }

returnnull;
    }
}

这个写法的好处就两个字：靠谱。 时间复杂度 O(m + n)，空间 O(1)，该交的作业都交了。

面试官更爱那种“两个指针互相跑”的写法

不过，说句实话，现在很多面试官更喜欢你写那个“看起来有点魔法”的双指针版本。 我第一次看到也一脸问号，后来想明白了还挺优雅的。

思路是这样的：

• 指针 p 从链表 A 开始走，走完 A 之后，跳到 B 的头
• 指针 q 从链表 B 开始走，走完 B 之后，跳到 A 的头
• 两个指针一直这样走，最终要么在相交点相遇，要么一起走到 null

Java 代码是这样：

publicclassSolution2{

public ListNode getIntersectionNode(ListNode headA, ListNode headB){
if (headA == null || headB == null) {
returnnull;
        }

        ListNode p = headA;
        ListNode q = headB;

// 最关键的一行就是 while (p != q)
while (p != q) {
// 走到尾巴就换头，否则就往下一个节点走
            p = (p == null) ? headB : p.next;
            q = (q == null) ? headA : q.next;
        }

// 要么是相交点，要么俩都是 null
return p;
    }
}

这段代码你第一次看肯定觉得“有点玄学”。 但你拉开算一下路程就懂了：

• 如果有交点，p 走的路：A 不相交那段 + 公共段 + B 不相交那段
• q 走的路：B 不相交那段 + 公共段 + A 不相交那段

两个人总路程是一样的，所以迟早会在公共段的起点撞上。 如果没有交点，那就是：

• p：A 全程 + B 全程
• q：B 全程 + A 全程

最后一起走到 null，p == q == null，while 退出，返回 null，刚刚好。

几个小细节，面试的时候顺嘴带一下

我当时和小李说，你要是真想在这个题上多拿点分，可以顺带提几句：

• 不能改链表结构（比如不能把 A 接到 B 后面去再找环之类），因为那样会破坏原数据结构
• 比较的是节点引用，不是值
• 这个解法时间 O(m + n)，空间 O(1)，挺符合面试里那种“最优解”的味道

讲到这，小李在公司楼下听完，当场说一句：“懂了懂了，我回去就把我那坨双重循环删了”。

行，就这样，我得去冲杯咖啡，等会儿还得改个 Bug，唉。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html