Skip to content

160. 相交链表 #61

Open
Open
@Geekhyt

Description

@Geekhyt

原题链接

双指针

  1. 借助双指针分别遍历链表 A 和 B。
  2. 遍历完自己后再将头指针指向另一个链表头部,继续遍历。
  3. 如果存在交点,则一定会相遇。
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)

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions