LeetCode LCR 023. 相交链表

Categories:

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

题目描述

✅ LCR 023. 相交链表

思路分析

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

核心思路：

用两个指针分别从 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
}

相似题目

题目	难度	考察点
141. 环形链表	简单	快慢指针
142. 环形链表 II	中等	环入口
206. 反转链表	简单	链表操作
234. 回文链表	简单	双指针
876. 链表的中间结点	简单	快慢指针

本文作者: HGNULB

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