代码随想录-DAY④-相交链表经典三解——leetcode 160
解法一:哈希集合
思路
将链表 A 中的每个节点都存入哈希集合,
遍历链表 B 并判断每一个节点,
如果发现已存在在哈希集合中的,说明相交,
如果遍历结束,说明不相交。
时间复杂度:O(m+n)
空间复杂度:O(m)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode *> visited;
ListNode * visit = headA;
while(visit != nullptr){
visited.insert(visit);
visit = visit->next;
}
visit = headB;
while(visit != nullptr){
if(visited.count(visit)){
return visit;
}
visit = visit->next;
}
return nullptr;
}
};
解法二:长度对齐
思路
遍历并计算两个链表的长度差,
让指向较长链表的指针向后挪动长度差的步数,
然后两个指针同时向后移动,
每走一步判断是否相等,
发现相等则存在相交,
走到头(一定同时)都不相等说明不相交。
时间复杂度:O(m+n)
空间复杂度:O(1)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *ptrA = headA, *ptrB = headB;
int lenA = 0, lenB = 0;
while (ptrA != nullptr) {
lenA++;
ptrA = ptrA->next;
}
while (ptrB != nullptr) {
lenB++;
ptrB = ptrB->next;
}
ptrA = headA, ptrB = headB;
if (lenA > lenB) {
for (int i=0; i<lenA-lenB; i++) {
ptrA = ptrA->next;
}
} else if (lenA < lenB) {
for (int i=0; i<lenB-lenA; i++) {
ptrB = ptrB->next;
}
}
while (ptrA != nullptr) {
if (ptrA == ptrB) {
return ptrA;
}
ptrA = ptrA->next;
ptrB = ptrB->next;
}
return nullptr;
}
};
解法三:双指针对调
思路
两个指向链表的指针同时向后移动,
任意一个走到头后,
都继而指向另一个链表头,
然后继续同时移动,
即最终两个指针一定走了一样的步数(n+m),
所以如果存在相交,
最后一定有一小段两指针重叠移动。
时间复杂度:O(m+n)
空间复杂度:O(1)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr){
return nullptr;
}
ListNode *ptrA = headA, *ptrB = headB;
while(ptrA != ptrB){
ptrA = ptrA==nullptr?headB:ptrA->next;
ptrB = ptrB==nullptr?headA:ptrB->next;
}
return ptrA;
}
};
原文地址:https://blog.csdn.net/weixin_43160551/article/details/140237621
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!