LeetCode 160. 相交链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：双指针交替遍历（推荐）
相似题目

题目描述

✅ 160. 相交链表

题目：

给定两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。若两个链表不存在相交节点，返回 null。题目数据保证链表中不存在环，函数返回结果后，链表必须保持其原始结构。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：两条链表不相交。

提示：

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

进阶：

能否设计一个时间复杂度 O(m + n)、仅用 O(1) 内存的解决方案？

思路分析

解法一：双指针交替遍历（推荐）

核心思路：

用两个指针分别从 headA 与 headB 出发，同步向前走。

指针走到链表尾后切换到另一条链表头部，两个指针总步数一致。

若存在相交点，两指针会在该结点相遇；否则最终同为 null。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为两条链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode p = headA;
        ListNode q = headB;

        // 双指针走完各自链表后切换，长度对齐后相遇
        while (p != q) {
            p = (p == null) ? headB : p.next;
            q = (q == null) ? headA : q.next;
        }

        return p;
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    p, q := headA, headB

    // 双指针各走一遍两条链表，长度对齐后相遇
    for p != q {
        if p == nil {
            p = headB
        } else {
            p = p.Next
        }
        if q == nil {
            q = headA
        } else {
            q = q.Next
        }
    }

    return p
}

相似题目

题目	难度	考察点
599. 两个列表的最小索引总和	简单	哈希表
141. 环形链表	简单	快慢指针
142. 环形链表 II	中等	环入口
206. 反转链表	简单	链表操作
234. 回文链表	简单	双指针
876. 链表的中间结点	简单	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/53571425