判断两个链表是否相交,若相交,求交点,考虑带环情况实现代码
程序员文章站
2022-07-14 14:49:09
...
梳理一下思路
思路
相当于求俩个链表的第一个公共结点,要么找到,要么为空,那么考虑到有链表可能有带环的情况,情况共分为下面三种:
(1)、两个链表都带环
分别获取两个链表环的入口点
判断入口点是否相同
如果入口点相同,临时修改链表为 Y 形状,处理完毕后恢复
如果入口点不相同,将一个环遍历一周看是否能遇到另外一个环的入口点(防止单独成环)(2)、两个链表都不带环
都无环,当做 Y 形状处理
(3)、一个带环一个不带环
这种情况肯定不相交,画几个图就想明白了。
关于(1),可以看下面这个图:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
// 找出链表的第一个公共结点
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
// 第一个公共结点
ListNode* commonNode = NULL;
if(pHead1 == NULL || pHead2 == NULL )
return NULL;
// (1) 判断是否都有环
ListNode* circleNode1; // 链表1 环上的结点(快慢指针相遇点),如果无环则为空
ListNode* circleNode2; // 链表2 环上的结点(快慢指针相遇点),如果无环则为空
circleNode1 = GetMeetNode(pHead1);
circleNode2 = GetMeetNode(pHead2);
// (2) 如果都有环 or 如果都无环 or 只有一个有环
// 1. 都有环
if (circleNode1 && circleNode2){
// 链表1 环的入口点
ListNode* circleEnterNode1 = GetCircleEnterNode(pHead1, circleNode1);
// 链表2 环的入口点
ListNode* circleEnterNode2 = GetCircleEnterNode(pHead2, circleNode2);
// 如果入口点相同,临时修改链表为 Y 形状,处理完毕后恢复
if(circleEnterNode1 == circleEnterNode2){
// 保存
ListNode* enterNodeNext = circleEnterNode1->next;
// 设置为 Y 形,即无环
circleEnterNode1->next = NULL;
// 调用处理无环情况的函数
commonNode = GetFirstCommonNodeNoCircle(pHead1, pHead2);
// 恢复
circleEnterNode1->next = enterNodeNext;
}// 如果入口点不同,将一个环遍历一周看是否能遇到另外一个环的入口点
else{
// 获取其中一个环的长度
int circleLength = GetCircleLength(circleNode2);
// 遍历一周看是否能遇到另外一个环的入口点,如果遇到则找到,否则未找到返回环
ListNode* next = circleEnterNode2->next;
// 遍历一圈
while(circleLength--){
// 找到公共结点
if(next == circleEnterNode1){
commonNode = circleEnterNode1;
break;
}
next = next->next;
}
// 未找到公共结点
if(circleLength <= 0)
return NULL;
}
} // 2. 都无环
else if (circleNode1 == NULL && circleNode2 == NULL){
commonNode = GetFirstCommonNodeNoCircle(pHead1, pHead2);
}
// (3).其中一个无环, 肯定无公共结点
return commonNode;
}
private:
// 获取带环链表环上的一个结点(快慢指针相遇点),如果不带环则返回空
ListNode* GetMeetNode(ListNode* pHead){
if(pHead == NULL)
return NULL;
ListNode* pFast = pHead;
ListNode* pSlow = pHead;
// 快慢指针法
while(pFast && pFast->next){
pFast = pFast->next->next;
pSlow = pSlow->next;
if(pFast == pSlow){
return pFast;
}
}
return NULL;
}
// 根据快慢指针相遇点,过去环的入口点
ListNode* GetCircleEnterNode(ListNode* pHead, ListNode* meetNode){
if(pHead == NULL || meetNode == NULL)
return NULL;
while(pHead != meetNode){
pHead = pHead->next;
meetNode = meetNode->next;
}
return pHead;
}
// 判断两个链表是否相交
bool isCross(ListNode* pHead1, ListNode* pHead2){
if(pHead1 == NULL || pHead2 == NULL){
return false;
}
while(pHead1->next)
pHead1 = pHead1->next;
while(pHead2->next)
pHead2 = pHead2->next;
if(pHead1 == pHead2)
return true;
return false;
}
// 获取链表长度
int getListLength(ListNode* pHead){
int length = 0;
while(pHead){
length++;
pHead = pHead->next;
}
return length;
}
// 处理 Y 形状
ListNode* GetFirstCommonNodeNoCircle(ListNode* pHead1, ListNode* pHead2){
if(pHead1 == NULL || pHead2 == NULL)
return NULL;
// 如果不相交,直接返回NULL
if (!isCross(pHead1, pHead2))
return NULL;
int step = 0;
int lengthList1 = getListLength(pHead1);
int lengthList2 = getListLength(pHead2);
step = lengthList1 - lengthList2;
if(step > 0){
while(step--)
pHead1 = pHead1->next;
}
else if(step<0){
while(step++)
pHead2 = pHead2->next;
}
while(pHead1 != pHead2){
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return pHead1;
}
// 获取带环链表环的长度
int GetCircleLength(ListNode* meetNode){
int length = 0;
if(meetNode == NULL)
return length;
ListNode* next = meetNode->next;
while(next != meetNode){
length++;
next = next->next;
}
return length;
}
};
上一篇: 遥感数据随机森林分类预测
下一篇: 遥感影像分类之SVM