NOTES · 学习笔记
相交链表
题目
如何才能找到相交的那个节点?
我们看示例 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 // 最后输出节点位置
}