题目
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解题思路:
我们将每个链表分为两部分,不相交部分和相交部分C
那么listA = A+C listB = B+C 他们的总长度为:A+C+B = B+C+A
所以我们只要找出两个节点相等的地方就是交点,因为他们只要相交的话一定会相遇的
逐步演示双指针过程
假设listA = [4,1,8] listB = [5,6,1,8]
初始状态
pA -> 4
pB -> 5
第1步:
pA = 4, pB = 5,不相等
pA = pA.next = 1
pB = pB.next = 6
第2步
pA = 1, pB = 6,不相等
pA = pA.next = 8
pB = pB.next = 1
第3步
pA = 8, pB = 1,不相等
pA = pA.next = None (链表A结束)
pB = pB.next = 8
第4步
pA = None, pB = 8,不相等
pA = headB = 5 (切换到链表B)
pB = pB.next = None
第5步
pA = 5, pB = None,不相等
pA = pA.next = 6
pB = headA = 4 (切换到链表A)
第6步
pA = 6, pB = 4,不相等
pA = pA.next = 1
pB = pB.next = 1
第7步
pA = 1, pB = 1,相等 ✓ 找到相交节点!
// 定义链表节点类
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
function getIntersectionNode (headA,headB){
if(!headA || !headB) return null;
let nodeA = headA
let nodeB = headB
while(nodeA !== nodeB ){
nodeA = nodeA !== null ? nodeA.next : headB
nodeB = nodeB !== null ? nodeB.next : headA
}
return nodeA
}
// 示例:手动创建链表并传入
// 创建 listA: 4 -> 1 -> 8 -> 4 -> 5
let a1 = new ListNode(4);
let a2 = new ListNode(1);
let a3 = new ListNode(8);
let a4 = new ListNode(4);
let a5 = new ListNode(5);
a1.next = a2;
a2.next = a3;
a3.next = a4;
a4.next = a5;
// 创建 listB: 5 -> 6 -> 1 -> 8 -> 4 -> 5
let b1 = new ListNode(5);
let b2 = new ListNode(6);
let b3 = new ListNode(1);
let b4 = new ListNode(8);
let b5 = new ListNode(4);
let b6 = new ListNode(5);
b1.next = b2;
b2.next = b3;
b3.next = b4;
b4.next = b5;
b5.next = b6;
// 设置相交点:listA 的第3个节点(8)与 listB 的第4个节点(8)相交
// 实际上是 listB 的第4个节点指向 listA 的第3个节点
b4.next = a3; // b4 (8) -> a3 (8)
let headA = a1;
let headB = b1;
console.log(getIntersectionNode(headA, headB)?.val); // 输出 8


![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)

