携手创作，共同成长！这是我参加「日新计划 8 月更文挑战」的第10天，点击查看活动详情

题目

给你两个单链表的头节点 headA 和 headB，请你找出并回来两个单链表相交的起始节点。假如两个链表不存在相交节点，回来 null。

图示两个链表在节点 c1 开端相交：

Swift - LeetCode - 相交链表

题目数据 确保整个链式结构中不存在环。

留意， 函数回来结果后，链表必须 保持其原始结构。

自定义评测：

评测体系的输入如下（你规划的程序 不适用 此输入）：

  • intersectVal – 相交的起始节点的值。假如不存在相交节点，这一值为 0
  • listA – 第一个链表
  • listB – 第二个链表
  • skipA – 在 listA 中（从头节点开端）跳到穿插节点的节点数
  • skipB – 在 listB 中（从头节点开端）跳到穿插节点的节点数

评测体系将根据这些输入创立链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。假如程序能够正确回来相交节点，那么你的解决方案将被视作正确答案。

示例 1：

Swift - LeetCode - 相交链表

  • 输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
  • 输出： Intersected at '8'
  • 解说： 相交节点的值为 8 （留意，假如两个链表相交则不能为 0）。 从各自的表头开端算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

Swift - LeetCode - 相交链表

  • 输入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
  • 输出： Intersected at '2'
  • 解说： 相交节点的值为 2 （留意，假如两个链表相交则不能为 0）。 从各自的表头开端算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

Swift - LeetCode - 相交链表

  • 输入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
  • 输出： null
  • 解说： 从各自的表头开端算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 因为这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可所以任意值。 这两个链表不相交，因而回来 null。

办法一：双指针

思路及解法

运用双指针的办法，能够将空间复杂度降至 O(1)。

只有当链表 headA 和 headB 都不为空时，两个链表才或许相交。因而首要判断链表 headA 和 headB 是否为空，假如其中至少有一个链表为空，则两个链表一定不相交，回来 nil。

当链表headA 和 headB 都不为空时，创立两个指针 pA 和 pB，初始时别离指向两个链表的头节点 headA 和 headB，然后将两个指针顺次遍历两个链表的每个节点。具体做法如下：

  • 每步操作需要一起更新指针 pA 和 pB。
  • 假如指针 pA 不为空，则将指针 pA 移到下一个节点；假如指针 pB 不为空，则将指针 pB 移到下一个节点。
  • 假如指针pA 为空，则将指针 pA 移到链表 headB 的头节点；假如指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
  • 当指针 pA 和 pB 指向同一个节点或许都为空时，回来它们指向的节点或许 nil。

证明 下面提供双指针办法的正确性证明。考虑两种状况，第一种状况是两个链表相交，第二种状况是两个链表不相交。 状况一：两个链表相交

链表 headA 和 headB 的长度别离是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a + c = m，b + c = n。

  • 假如 a = b，则两个指针会一起抵达两个链表相交的节点，此刻回来相交的节点
  • 假如 a != b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会一起抵达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a + c + b 次、指针pB 移动了 b + c + a 次之后，两个指针会一起抵达两个链表相交的节点，该节点也是两个指针第一次一起指向的节点，此刻回来相交的节点。

状况二：两个链表不相交

链表headA 和 headB 的长度别离是 m 和 n。考虑当 m = n 和 m != n 时，两个指针别离会如何移动：

  • 假如 m = n，则两个指针会一起抵达两个链表的尾节点，然后一起变成空值 nil，此刻回来 nil；
  • 假如 m != n，则因为两个链表没有公共节点，两个指针也不会一起抵达两个链表的尾节点，因而两个指针都会遍历完两个链表，在指针 pA 移动了 m + n 次、指针 pB 移动了 n + m 次之后，两个指针会一起变成空值 nil，此刻回来 nil。

代码

class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        if nil == headA || nil == headB {
            return nil
        }
        var pA: ListNode? = headA
        var pB: ListNode? = headB
        while pA != pB {
            pA = pA == nil ? headB : pA?.next
            pB = pB == nil ? headA : pB?.next
        }
        return pA
    }
}
extension ListNode: Equatable {
    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        return lhs === rhs
    }
}

复杂度剖析

  • 时刻复杂度：时刻复杂度：O(m+n)，其中 m 和 n 是别离是链表 headA 和 headB 的长度。两个指针一起遍历两个链表，每个指针遍历两个链表各一次。

  • 空间复杂度：O(1)。