两个链表的第一个重合节点

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

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

image-20230714161932431

  1. 题目数据 保证 整个链式结构中不存在环。
  2. 函数返回结果后，链表必须 保持其原始结构 。

1.哈希表

主要思路：

  1. 遍历listA将其中的结点全部标记存入unset中（哈希表）
  2. 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果
  3. 若遍历listB都完都没有出现符合要求的结果则返回nullptr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//注：将unordered_set放到成员方法内部可以提高时间效率
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> unset;
        //1.initialize unset
        ListNode* tmp = headA;
        while (tmp) {
            unset.insert(tmp);
            tmp = tmp->next;
        }
        //2.find the first node
        tmp = headB;
        while (tmp) {
            if (unset.count(tmp)) return tmp;
            tmp = tmp->next;
        }
        return nullptr;
    }
};

时间：48ms

内存：16.24mb

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

2.双指针

主要思路：

  1. 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr
  2. 当链表都不为空时 创建两个指针pA和pB 初始时分别指向链表的头节点
  3. 将两个指针依次遍历两个链表的每个节点
    • 如果指针pA不为空，则将指针pA移到下一个节点；如果指针pB不为空，则将指针pB移到下一个节点
    • 如果指针pA为空 则将指针pA移动到链表headB的头结点 如果指针pB为空 则将指针pB移动到链表headA的头结点
    • 当指针pA和pB指向同一个结点或者都为空时 返回他们指向的结点或者null

过程证明：

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

  • 情况一：两个链表相交
  • 链表 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，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 nullptr，此时返回 nullptr；
    • 如果 m≠n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 nullptr，此时返回 nullptr。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode *pa = headA, *pb = headB;
        while (pa != pb) {
            //pa = (pa == nullptr ? headB : pa->next);
            pa = pa == nullptr ? headB : pa->next;
            pb = pb == nullptr ? headA : pb->next;
        }
        return pa;
    }
};
  • 时间复杂度：$O(m+n)$ 两个指针同时遍历两个链表，每个指针遍历两个链表各一次
  • 空间复杂度：$O(1)$