相交链表

GitHub跳转原题关系图返回列表

双指针分别走 A+B 和 B+A，长度差被抵消后在交点或 nullptr 相遇。

OJ: leetcodecn

题目 ID: intersection-of-two-linked-lists

难度:入门

标签:链表双指针哈希表cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

找到两个单链表相交的起始节点。若不相交返回 nullptr。

思路

哈希集合存 A 节点再遍历 B 查找 O(m+n) 空间。双指针 O(1) 空间：两指针分别从 A、B 出发，走到尾后跳到另一链表头部。由于总路程 A+B = B+A，它们一定在交点或 nullptr 处相遇。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：双指针走 A+B、B+A 消除长度差，O(m+n) O(1)。
#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB)
            return nullptr;
        auto a = headA, b = headB;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};

ListNode *build(istream &in, int n) {
    if (!n)
        return nullptr;
    auto head = new ListNode(0), cur = head;
    for (int i = 0, v; i < n; i++) {
        in >> v;
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return head->next;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    auto a = build(cin, n), b = build(cin, m);
    auto ans = Solution().getIntersectionNode(a, b);
    cout << (ans ? ans->val : -1) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        a, b = headA, headB
        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a


def build(arr):
    dummy = cur = ListNode(0)
    for v in arr:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def main() -> None:
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ha, hb = build(a), build(b)
    ans = Solution().getIntersectionNode(ha, hb)
    print(ans.val if ans else -1)


if __name__ == "__main__":
    main()

复杂度

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

总结

走完自己的路再走别人的路——长度差被抵消，交汇处自然相遇。