链表

相交链表

简单#160Java时间 O(m+n)空间 O(1)

题目要做什么

两条无环单链表可能共享同一段尾部,返回第一个公共节点。相交按节点身份判断,值相同不代表相交;示例输出是公共节点的值。skipA、skipB 表示公共部分的起始下标,均为 −1 表示不相交。

题目示例输入listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
题目示例输出8

01 为什么这样做

两个指针分别遍历 A→B 和 B→A。走完一条链就切换到另一条,两者走过的总长度相同,会在公共起点或 null 相遇。

始终成立的条件

切换链表后,两个指针消除了两条链的长度差。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {3        ListNode a = headA, b = headB;4        while (a != b) {5            a = a == null ? headB : a.next;6            b = b == null ? headA : b.next;7        }8        return a;9    }10}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索