目录
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;
}
};
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。