题目

image

暴力

思路：对 A 中每个节点，遍历一遍 B，看是否有节点地址相同（注意是判断节点引用相等，不是值相等）。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        for (ListNode *pa = headA; pa != nullptr; pa = pa->next) {
            for (ListNode *pb = headB; pb != nullptr; pb = pb->next) {
                if (pa == pb) return pa;
            }
        }
        return nullptr;
    }
};
  • 时间复杂度：O(m × n)
  • 空间复杂度：O(1)

优化

思路：用空间换时间，先把 A 的所有节点地址存进哈希集合，再遍历 B，第一个能在集合中找到的节点就是交点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <unordered_set>

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        std::unordered_set<ListNode*> visited;
        for (ListNode *p = headA; p != nullptr; p = p->next) {
            visited.insert(p);
        }
        for (ListNode *p = headB; p != nullptr; p = p->next) {
            if (visited.count(p)) return p;
        }
        return nullptr;
    }
};

  • 时间复杂度：O(m + n)
  • 空间复杂度：O(m)

最优

让两个指针分别从 A、B 出发，走到末尾后跳到对方链表头部继续走。两个指针总路程都是 m + n，若有交点会在第二轮相遇，无交点则同时变为 nullptr。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;

        ListNode *pa = headA;
        ListNode *pb = headB;

        while (pa != pb) {
            pa = (pa == nullptr) ? headB : pa->next;
            pb = (pb == nullptr) ? headA : pb->next;
        }

        return pa;
    }
};

  • 时间复杂度：O(m + n)
  • 空间复杂度：O(1)
  • 原理：设 A 独有部分长度 a，B 独有部分长度 b，公共部分长度 c。pa 走的路径是 a + c + b，pb 走的路径是 b + c + a，路程相等，所以必定在公共起点相遇（无交点时 c = 0，两者同时到达 nullptr）。

拿题目示例 1 验证一下

listA = [4,1,8,4,5]，listB = [5,6,1,8,4,5]，skipA=2, skipB=3

a = 2（A 独有：4, 1）
b = 3（B 独有：5, 6, 1）
c = 3（公共：8, 4, 5）

pa 走法：4→1（a=2 步）→8→4→5（c=3 步，到达 null，共 5 步）→跳到 headB→5→6→1（b=3 步）→到达”8”这个节点。总步数 = 2+3+3 = 8。

pb 走法：5→6→1（b=3 步）→8→4→5（c=3 步，到 null，共 6 步）→跳到 headA→4→1（a=2 步）→到达”8”这个节点。总步数 = 3+3+2 = 8。

两者都是 8 步，同时到达同一个节点对象”8”，不仅长度相等，而且是同一个内存节点（因为交点之后 A 和 B 本来就是同一段链表，天然共享节点）。所以 pa == pb 成立，循环退出。

趣味评论小剧场

你们之所以相遇，正是因为你走了 ta 走过的路，而 ta 也刚好走了你走过的路。这是何等的缘分！
而当你们携手继续走下去时，你会慢慢变成 ta 的样子，ta 也会慢慢变成你的样子。