Open
Description
双指针
- 借助双指针分别遍历链表 A 和 B。
- 遍历完自己后再将头指针指向另一个链表头部,继续遍历。
- 如果存在交点,则一定会相遇。
const getIntersectionNode = function(headA, headB) {
if (headA === null || headB === null) {
return null
}
let pA = headA, pB = headB
while (pA !== pB) {
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return pA
}
- 时间复杂度:O(m + n)
- 空间复杂度:O(1)