本文主要是介绍链表相交 三种思路 C++ 代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
方法1 回环法 讲listA & listB看成一个环
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//回环法 讲listA & listB看成一个环
//e.g listA = [9,1,8,4,5] listB = [1,8,4,5]
// posA=4 ,posB =5
// goon posA=5 posB=9
// goon posA= 1 ,posB=1 ,ok finish
ListNode * posA= headA,*posB = headB;
bool AExchangeFlag=false;
if(!headB || !headA ) return NULL;
while(!AExchangeFlag || posA )
{
if(posA == posB ) return posA;
posA= posA->next;
posB = posB->next;
//在A没有执行交换情况下
if(!AExchangeFlag && posA== NULL ) {
AExchangeFlag=true;
posA= headB;
}
if(posB==NULL ) posB = headA;
}
return NULL;
}
};
方法2 stack 法,从后往前找到第一个不等的地方
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//stack 法,找到第一个不等的地方
//e.g listA = [9,1,8,4,5] listB = [1,8,4,5]
// stackA =9 != listB=NULL, return --listA
std::stack<ListNode*> stackA, stackB;
while(headA)
{
stackA.push(headA);
headA= headA->next;
}
while(headB)
{
stackB.push(headB);
headB = headB->next;
}
if(stackA.size()< stackB.size() ) std::swap(stackA,stackB);
ListNode * preA= NULL;
while(!stackB.empty())
{
auto tA= stackA.top(); stackA.pop();
auto tB= stackB.top(); stackB.pop();
if(tA!= tB) return preA;
preA = tA;
}
return preA;
}
};
方法3 对齐法 先计算出长度差
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 对齐法 先计算出长度差
// listA = [9,1,8,4,5] listB = [7,8,4,5]
// posA= 1 ,posB=7
// posA=8 ,pos=8 ok
auto posA= headA, posB= headB;
//to get lenA ,lenB
int lenA=0,lenB=0;
while(posA) {
lenA++;
posA= posA->next;
}
while(posB)
{
lenB++;
posB= posB->next;
}
if(lenA < lenB )
{
std::swap(headA,headB);
std::swap(lenA,lenB);
}
int difLen= lenA-lenB;
posA = headA;
while(difLen)
{
posA= posA->next;
difLen--;
}
//now same len
posB= headB;
while(posA)
{
if(posA == posB) return posA;
posA= posA -> next;
posB= posB -> next;
}
return NULL;
}
};
这篇关于链表相交 三种思路 C++ 代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!