160 相交链表
容易理解的方法
- 计算两个链表的长度
- 计算长度差gap
- 长的一侧先走gap个长度,走完后,两个链表处于同一长度
- 两个链表同时遍历,如果p1 == p2,则相遇;如果p1(p2) == nullptr,说明无法相遇
/**
* 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) {
ListNode *p1 = headA, *p2 = headB;
int lenA = 0, lenB = 0;
while (p1) {
lenA++;
p1 = p1->next;
}
while (p2) {
lenB++;
p2 = p2->next;
}
p1 = headA;
p2 = headB;
if (lenB > lenA) {
swap(lenB, lenA);
swap(p1,p2);
}
int gap = lenA - lenB;
while (gap--) {
p1 = p1->next;
}
while (p1) {
if(p1 == p2)
return p1;
p1 = p1->next;
p2 = p2->next;
}
return nullptr;
}
};
- 时间复杂度:O(n + m)
- 空间复杂度:O(1)
难以理解的方法
第一轮:
各自遍历链表,短的一侧到达终点需要走A+C,而长的一侧到达终点需要走B+C,长度之差为B-A。
如果想要抹平两者之间长度之差,使两者同时到达相交点,那么需要让短的一侧比长的一侧多走B-A。我们发现,当短的一侧到达终点,长的一侧需要走B-A才能到达终点,若此时让短的一侧转为走长的一侧,那么当长的一侧到达终点,短的一侧恰好弥补了B-A的长度差,此时两者步数之和相同。
第二轮: 各自遍历链表,两者相遇即为相交点。如果不相遇,则没有相交。
结论:
由于每个指针都需要走A + B + C,两个指针最后一定相等 - 如果两个指针都为nullptr,说明没有相交点 - 否则,两个指针等于相交点指针
/**
* 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) {
ListNode* p1 = headA, * p2 = headB;
while(p1 != p2){
if(p1 == nullptr)
p1 = headB;
else
p1 = p1->next;
// 注意这里是if,因为p1和p2的判断是互相独立的
if(p2 == nullptr)
p2 = headA;
else
p2 = p2->next;
}
return p1;
}
};
/**
* 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 *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};