Intersection of Two Linked Lists

题目介绍

LeetCode 160. Intersection of Two Linked Lists。

复杂度

时间复杂度: O(m+n), 空间复杂度: O(1)

解题思路

主要的思路是消除两个链表的长度差。

• 指针 pA 指向 A 链表，指针 pB 指向 B 链表，往后遍历
• 如果 pA 到了尾指针，则 pA = headB 继续遍历
• 如果 pB 到了尾指针，则 pB = headA 继续遍历

这样的话就会消除长度差，并且在交点处相遇，还是个数学问题。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    public func getIntersectionNode(headA: ListNode?, headB: ListNode?) -> ListNode? {
        guard headA != nil && headB != nil else {
            return nil
        }
        var pA = headA
        var pB = headB
        while pA !== pB {
            pA = pA == nil ? headB : pA?.next
            pB = pB == nil ? headA : pB?.next
        }
        return pA
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/12/IntersectionOfTwoLinkedLists/