目录
2024-03-12 leetcode写题记录
160. 相交链表
题目链接
题意
给你两个单链表的头节点\(headA\)和\(headB\)，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回\(null\)。
图示两个链表在节点\(c1\)开始相交：
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
节点定义：
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
解法
解法一
刚看到这道题，想了下数学公式。
一、先遍历一遍A和B，看结尾是否相同，不同则意味着没有公共部分，返回nullptr。
二、如果结尾相同，设A链独有的长度为a，B链独有的长度为b，共有的长度为c。
（1）先从A开头遍历一遍，得到长度x，则x=a+c，同时反转整个A链；
（2）再从从B开头遍历一遍，得到长度y，则y=a+b，同时反转现在的链（即A独有部分和B独有部分串起来）；
（3）最后从公共结尾开始遍历，得到长度z，则z=b+c，同时反转整个链（也就是整个B链），那么图形会变成初始模样。
可以得到：
\(
\left\{
\begin{aligned}
a+c=x\\
a+b=y\\
b+c=z
\end{aligned}
\right.
\)
所以，A链独有部分的长度为\(\frac{x+y-z}{2}\)，根据长度返回对应点就行
当没有公共点时，上述式子第二个等式不成立，所以不等式组是错误的，不能直接计算出长度，这也是为什么要分两种情况讨论，而不是直接求出c的长度判断是否为0。
class Solution {
public:
// 查链有多长，还可以选择是否反转链表
int f(ListNode*& head, bool rvs = false) {
int cnt = 0;
ListNode *last = nullptr, *to = nullptr;
while (head != nullptr) {
cnt++;
to = head->next;
if (rvs) head->next = last;
last = head;
head = to;
}
head = last;
return cnt;
}
ListNode* getLast(ListNode* x) {
ListNode* last = nullptr;
while (x != nullptr) {
last = x;
x = x->next;
}
return last;
}
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (getLast(headA) != getLast(headB)) return nullptr;
ListNode *ha = headA;
int x = f(headA, true), y = f(headB, true), z = f(headA, true), a = (x + y - z) / 2;
while (a--) ha = ha->next;
return ha;
}
};
解法二
看评论区，有更巧妙的想法：
如果两个链有相交，那么可以让两个指针分别从两个链开端进行遍历，每个指针遍历结束之后，都让指针跳到另一个链的开端继续遍历，这样当两个指针相同时，他们就都遍历了整个图，并且相聚在相交点。
两种写法时间复杂度上一样，但解法二写起来简单得多。
class Solution {
public:
ListNode* getLast(ListNode* x) {
ListNode* last = nullptr;
while (x != nullptr) {
last = x;
x = x->next;
}
return last;
}
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (getLast(headA) != getLast(headB)) return nullptr;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a == nullptr ? headB : a->next;
b = b == nullptr ? headA : b->next;
}
return a;
}
};