NOTES · 学习笔记

相交链表

LeetCode链表 · 简单约 4 分钟

题目

如何才能找到相交的那个节点?

我们看示例 1。A 的单独部分是 4-1,共两个元素;B 的单独部分是 5-6-1,共三个元素;然后来到公共部分 8-4-5。

我们借助指针来模拟一遍路线。a 指针刚开始指向 A 的头节点 4,b 指针刚开始指向 B 的头节点 5。

两个指针分别移动

step1:A 从 4 走到 1,B 从 5 走到 6。

step2:A 从 1 走到 8,B 从 6 走到 1。

step3:A 从 8 走到 4,B 从 1 走到 8。

step4:A 从 4 走到 5,B 从 8 走到 4。

step5:A 从 5 走到 nil,B 从 4 走到 5。

目前 A 走到了 nil 的位置,而 B 还没有走到。如果 A 直接停在这里,就没办法继续比较了,所以让 A 指针重新回到 B 的头节点,继续走 B 的路线。

A:4 → 1 → 8 → 4 → 5 → nil
B:5 → 6 → 1 → 8 → 4 → 5

为什么要切换头节点

这样做的目的是让两个指针分别走完 A+B 和 B+A,抵消两条链表的长度差,让它们最终在相交节点相遇。

step6:A 从 nil 切换到 B 的头节点 5,B 从 5 走到 nil。

step7:A 从 5 走到 6,B 从 nil 切换到 A 的头节点 4。

step8:A 从 6 走到 1,B 从 4 走到 1。

step9:A 从 1 走到 8,B 从 1 走到 8。

走到这里,两个指针都指向了公共部分的起始节点 8,也就是它们指向了同一个节点。此时 pa == pb,循环结束,直接返回 pa,也就是相交节点 8。

如果两个链表没有相交,两个指针最终都会走到 nil,循环同样会结束,最后返回 nil。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pa, pb := headA, headB // 定义两个指针,pa 指向 headA 头节点,pb 指向 headB 头节点
    for pa != pb {         // 当 pa 和 pb 还没有相遇时继续循环
        if pa == nil {     // pa 指向自己最后的位置
            pa = headB      // pa 走到 nil,切换到 b 的头节点位置走 b 的路线
        } else {
            pa = pa.Next     // 如果 pa 自己的路线没走完,就继续走下一步
        }
        if pb == nil {      // pb 同理
            pb = headA
        } else {
            pb = pb.Next
        }
    }
    return pa // 最后输出节点位置
}