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

一、题目介绍

二、解题思路

三、代码

一、题目介绍

题目链接：面试题 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 开始，两个链表共享同一条路径。

这也意味着：

如果 A 和 B 相交，它们从交点开始的所有节点必须完全相同（即相同地址，而不仅仅是相同值）。
如果 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;}

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

时间复杂度分析

我们来逐步分析该算法的时间复杂度：
计算链表A的长度
while(curA!=nullptr){lensizeA++;curA=curA->next;
}
该循环遍历了一次链表A，因此时间复杂度为 O(m)（其中 m 是链表A的长度）。
计算链表B的长度
while(curB!=nullptr){lensizeB++;curB=curB->next;
}
该循环遍历了一次链表B，因此时间复杂度为 O(n)（其中 n 是链表B的长度）。
让 curA 移动 diff 步
while(diff){curA = curA->next;diff--;
}
这里最多执行 O(m - n) 次（即链表A比链表B长多少），在最坏情况下，链表A和B长度相等，则此步执行 0 次。
同时遍历 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)