LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

Categories:

Tags:

题目描述
思路分析
1. 解法一：双指针（推荐）
2. 解法二：哈希表
相似题目

题目描述

✅ 剑指 Offer 52. 两个链表的第一个公共节点

思路分析

解法一：双指针（推荐）

核心思路：

设链表 A 长度为 a，链表 B 长度为 b，公共部分长度为 c。

指针 pA 从 headA 出发，走完 A 后跳到 headB；指针 pB 从 headB 出发，走完 B 后跳到 headA。

pA 共走 a + c + b 步，pB 共走 b + c + a 步，两者步数相同，最终在公共节点处相遇。

若无公共节点，两指针最终同时走到 nil，循环结束。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为链表 A 和链表 B 的长度

空间复杂度：O(1)，只使用了常量额外空间

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        // 两指针各走 a+b+c 步后必在公共节点相遇，无公共节点时同时到达 null
        while (pA != pB) {
            // 走完自身链表后切换到对方头节点
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pA, pB := headA, headB
    // 两指针各走 a+b+c 步后必在公共节点相遇，无公共节点时同时到达 nil
    for pA != pB {
        // 走完自身链表后切换到对方头节点
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

解法二：哈希表

核心思路：

先遍历链表 A，将所有节点存入哈希集合。

再遍历链表 B，第一个出现在哈希集合中的节点即为公共节点。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为链表 A 和链表 B 的长度

空间复杂度：O(m)，其中 m 为链表 A 的节点数，用于存储哈希集合

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 将链表 A 的所有节点加入哈希集合
        Set<ListNode> visited = new HashSet<>();
        for (ListNode cur = headA; cur != null; cur = cur.next) {
            visited.add(cur);
        }
        // 遍历链表 B，找到第一个已在集合中的节点
        for (ListNode cur = headB; cur != null; cur = cur.next) {
            if (visited.contains(cur)) {
                return cur;
            }
        }
        return null;
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 将链表 A 的所有节点加入哈希集合
    visited := make(map[*ListNode]bool)
    for cur := headA; cur != nil; cur = cur.Next {
        visited[cur] = true
    }
    // 遍历链表 B，找到第一个已在集合中的节点
    for cur := headB; cur != nil; cur = cur.Next {
        if visited[cur] {
            return cur
        }
    }
    return nil
}

相似题目

题目	难度	考察点
160. 相交链表	简单	双指针 / 哈希表
141. 环形链表	简单	快慢指针 / 环检测
142. 环形链表 II	中等	快慢指针 / 入环节点
21. 合并两个有序链表	简单	双指针 / 链表合并
876. 链表的中间结点	简单	快慢指针
234. 回文链表	简单	快慢指针 + 反转
19. 删除链表的倒数第 N 个结点	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/43219443