题目链接

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

示例

示例1：

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

提示

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 0 <= m, n <= 3 * 10
  • 1 <= Node.val <= 10
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0

  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

    思路

    思路1：计数

    若有交点，则从交点开始，两个链表的结点是一样的。不失一般性，我们设 listA 长度大于 listB 。将两个链表的尾部对齐，将 listA 的指针移动到与 listB 头部对齐的位置，然后两个指针同时移动，判断两个指针是否相等即可。

    思路2：双指针

    首先我们假设两个链表有交点，listA 的长度为 a ，起点到交点的距离为 x ； listB 的长度为 b ，起点到交点的距离为 y 。
    因为则从交点开始，两个链表的结点是一样的，所以我们有 a - x = b - y ，移项得 a + y = b + x 。
    换言之，将 listA 后面接上 listB ，listB 后面接上 listA ，两个指针分别从两个链表的头部开始移动，它们一定会同时到达交点。
    如果两个链表没有交点，那么指针最终会移动到尾部，然后变成 nullptr 。

    题解

    思路2：双指针

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode(int x) : val(x), next(NULL) {}
    7. * };
    8. */
    9. class Solution {
    10. public:
    11.   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    12.       ListNode* a = headA;
    13.       ListNode* b = headB;
    14.       while (a != b) {
    15.           a = a != nullptr ? a->next : headB;
    16.           b = b != nullptr ? b->next : headA;
    17.       }
    19.       return a;
    20.   }
    21. };

    复杂度分析

    思路2：双指针

  • 时间复杂度：02.07. 链表相交 - 图1

  • 空间复杂度：02.07. 链表相交 - 图2