当前位置： 首页 > article >正文

leetcode面试题-------链表相交

article 2025/3/12 14:20:36

目录

一、题目介绍

二、解题思路

三、代码

一、题目介绍

题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

问1：[4,1,8,4,5]和[5,0,1,8,4,5]的相交节点为什么不是1啊？

答：该题交点不是数值相等，而是指针相等！注意是指针哦！

假设指针P1指向[4,1,8,4,5]里的1，地址是001。

假设指针P2指向[5,0,1,8,4,5]里的1，地址是002。

虽然两个指针指向的节点值相同，但是地址不同，所以这并不是同一个节点，也就不是题目的交点。

问2：那为什么后面这个8的地址就相等了呢。。。。

答：注意看测试用例
listA = [4,1,8,4,5], listB = [5,1,1,8,4,5]; skipA=2,skipB=3
后面的2和3意思就是题目指定了只有分别从这两个位置开始，才是指向同一个地址。
通过这种方式模拟了底层的逻辑，把2,3改成1,2就是从1开始相等了。

 

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

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

二、解题思路

在单链表结构中，一个节点只能有一个 next 指针，指向下一个节点。因此：如果 A 和 B 存在交点（即指针相同，而不是值相等），那么交点之后的所有节点也必须是相同的（即共享同一段尾部）。

在单链表的结构中，每个节点只有一个 next 指针指向下一个节点，因此如果两个链表 A 和 B 存在交点，那么交点之后的所有节点都必须是相同的（即共享同一段尾部）。

详细分析

假设两个链表 A 和 B 在某个节点 X 相交，形成如下结构：

A: a1 → a2 → a3
                   \
                    X → x1 → x2 → x3  (公共部分)
                   /
B: b1 → b2

在 X 之前，链表 A 和 B 可能是独立的，但一旦相交，它们的 next 指针指向的是同一个节点，意味着从 X 开始，两个链表共享同一条路径。

这也意味着：

  1. 如果 A 和 B 相交，它们从交点开始的所有节点必须完全相同（即相同地址，而不仅仅是相同值）。
  2. 如果 A 和 B 没有交点，那么它们的所有节点都是独立的。

为什么交点之后必须共享尾部？

因为 单链表的节点只有一个 next 指针，如果 A 和 B 在 X 处相交：

  • X 之后的所有节点 x1 → x2 → x3 都是 相同的对象，即 next 指向的是同一个地址。
  • 这意味着 X 之后的部分必须完全相同，否则就会破坏链表的单向结构。

换句话说：

  • 不能出现 交点之后 A 和 B 分别走向不同的路径，比如： 
    A: a1 → a2 → a3
                   \
                    X → x1 → x2 (A独有)
                   /
B: b1 → b2 → y1 → y2 (B独有)  ❌（不可能）
    这种情况在单链表中是不可能的，因为 X 只有一个 next，无法同时指向 x1 和 y1。

结论

如果两个单链表存在交点，那么交点之后的所有节点必然是共享的。这也是为什么在 getIntersectionNode 这样的算法中，我们可以通过比对节点地址来找到交点，而不需要考虑值是否相等。

因此，如果存在交点，我们需要对齐 A 和 B 的长度，然后同步移动指针去找到第一个相交的节点（即 curA == curB 的位置）。

  • 步骤1：计算 A 和 B 的长度 lenA 和 lenB。
  • 步骤2：计算长度差 diff = |lenA - lenB|。
  • 步骤3：让较长的链表指针先前进 diff 步，使得两者对齐到相同的剩余长度。
  • 步骤4：同时移动 curA 和 curB，找到第一个相交的节点。

图例展示上述步骤：

 

三、代码

完整代码如下： 

// 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
#include<iostream>

// 链表节点结构体
struct LinkNode{
    int data; // 定义数据域
    LinkNode* next; //定义指针域
    LinkNode(int x):data(x),next(nullptr){}; // 节点的构造函数
};


LinkNode* getIntersectionNode(LinkNode *headA, LinkNode *headB) { // 链表A的长度要大于链表B的长度
    // 定义两个链表的遍历指针，初始化让他们均指向各自链表的头节点
    LinkNode* curA = headA;
    LinkNode* curB = headB;
    // 计算链表A的长度
    int lensizeA=0;
    while(curA!=nullptr){
        lensizeA++;
        curA=curA->next;
    }
    // 计算链表B的长度
    int lensizeB=0;
    while(curB!=nullptr){
        lensizeB++;
        curB=curB->next;
    }
    // 再让curA与curB重新指向各自链表头节点
    curA=headA;
    curB=headB;

    //计算两个链表长度差值
    int diff = lensizeA-lensizeB; 
    // 让curA移动diff步，使得curA指向的后半部分链表与curB指向的链表元素个数相等
    while(diff){
        curA = curA->next;
        diff--;
    }

    // 此时，同时开始遍历，遇到节点地址相同的直接返回
    while(curA!=nullptr){
        if(curA == curB){ 
            return curA;
        }
        // 指针向后移动，继续遍历下一个节点
        curA=curA->next;
        curB=curB->next;
    } 
    return nullptr; // 如果没找到具有相同地址的节点，直接返回nullptr
}

int main(){
    // 链表A: 0--3--1--2--4 【链表A的长度长于链表B的长度】
    LinkNode* headA = new LinkNode(0);
    headA->next = new LinkNode(3);
    headA->next->next = new LinkNode(1);
    headA->next->next->next = new LinkNode(2);
    headA->next->next->next->next= new LinkNode(4);

    // 链表B: 3--2--4【链表B的长度小于链表A的长度】
    LinkNode* headB = new LinkNode(3);
    headB->next = headA->next->next->next;
    headB->next->next = headA->next->next->next->next;
   
    LinkNode* intersectnodeval = getIntersectionNode(headA, headB);
    std::cout<<"相交的节点值为:";
    std::cout<<intersectnodeval->data<<std::endl;

}

时间复杂度、空间复杂度分析

时间复杂度分析

我们来逐步分析该算法的时间复杂度：

  1. 计算链表A的长度

    while(curA!=nullptr){
    lensizeA++;
    curA=curA->next;
}

    该循环遍历了一次链表A，因此时间复杂度为 O(m)（其中 m 是链表A的长度）。

  2. 计算链表B的长度

    while(curB!=nullptr){
    lensizeB++;
    curB=curB->next;
}

    该循环遍历了一次链表B，因此时间复杂度为 O(n)（其中 n 是链表B的长度）。

  3. 让 curA 移动 diff 步

    while(diff){
    curA = curA->next;
    diff--;
}

    这里最多执行 O(m - n) 次（即链表A比链表B长多少），在最坏情况下，链表A和B长度相等，则此步执行 0 次。

  4. 同时遍历 curA 和 curB 进行比对

    while(curA!=nullptr){
    if(curA == curB){ 
        return curA;
    }
    curA=curA->next;
    curB=curB->next;
}

    该循环最多遍历 O(n) 次（因为curA和curB此时从相同长度的部分同时前进，最坏情况下遍历到链表末尾）。

综上，总体时间复杂度为：

O(m)+O(n)+O(m−n)+O(n)=O(m + n)

因此，该算法的 时间复杂度为 O(m+n)。

空间复杂度分析

该算法只使用了 常数级别 的额外变量：

  • curA, curB（两个指针）
  • lensizeA, lensizeB（两个整型变量）
  • diff（一个整型变量）

所有这些额外使用的空间 与输入链表的大小无关，因此 空间复杂度为 O(1)。

结论

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


http://www.kler.cn/a/576627.html

相关文章：

  • c语言笔记 fgets
  • Maven匹配机制和仓库库设置
  • *算法中的数据结构(3)
  • 【神经网络】python实现神经网络（一）——数据集获取
  • 【hello git】git rebase、git merge、git stash、git cherry-pick
  • 实现Django和Transformers 构建智能客服大模型（模拟订单系统）
  • 【每日学点HarmonyOS Next知识】双向传值问题、子组件半径、VIdeo标签下载隐藏、字符串替换、路由问题
  • 2025年科技趋势深度解析：从“人工智能+”到量子跃迁的技术革命
  • Qt：多线程
  • 通过Nacos API实现微服务不间断部署
  • Linux中的序列化和反序列化与网络计算器
  • 2025系统架构师（一考就过）：案例之五：典型架构、架构演化、人工智能、云计算、大数据
  • 数据库基础练习1
  • 什么是 kafka
  • 无人机应用探索：玻纤增强复合材料的疲劳性能研究
  • GOPATH和Go Modules模式
  • 机器学习常见面试题
  • Kubernetes中的 iptables 规则介绍
  • 一、MySQL备份恢复
  • 【LangChain】Python Web框架推荐