五种方法解决链表的第一个公共子节点问题
题目：剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
链表节点的定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
小技巧：
如果题目刚拿到手的时候没有思路怎么办？
试着将常用的数据结构和常用的算法思想都想一遍，一个一个靠，看有没有能解决的。
常用的数据结构：数组，链表，队列，栈，Hash表，集合，树，堆等等
常用的算法：各种排序，双指针，递归等等
按照这个思路，想一想
（1）方法一： 首先想到的就是暴力破解，用一个双层循环遍历来一个一个对比找相同的那个节点，这样时间复杂度就会有点高，O(n^2)
（2）方法二： 既然时间复杂度比较高的话，那我们就想想用空间换时间，数组？链表？队列？栈？
欸，这个可以。既然两个链表尾巴是一致的，那将两个链表分别放到栈里面，根据栈先进后出的特性，相当于就是从尾到头地遍历链表嘛。
在出栈过程中，对比两边的节点，若相同则继续出栈比较，若不相同，则上一个出栈的节点就是公共节点。
这样时间复杂度就降到O(n)，空间复杂度为O(n)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 将链表A存放到栈A中
stack<ListNode*> stackA;
while (headA != nullptr) {
stackA.push(headA);
headA = headA->next;
}
// 将链表B存放到栈B中
stack<ListNode*> stackB;
while (headB != nullptr) {
stackB.push(headB);
headB = headB->next;
}
ListNode* intersectionNode = nullptr;
ListNode* tempA = nullptr;
ListNode* tempB = nullptr;
// 同时出栈进行比较
while(!stackA.empty() && !stackB.empty()) {
tempA = stackA.top();
tempB = stackB.top();
stackA.pop();
stackB.pop();
// 当遇到不一样的节点时，证明上一个出栈的即为公共节点，就是当前节点的下一个节点
if (tempA != tempB) {
break;
}
}
// 结束while的可能性有两种：
// 1. 碰到了不同的节点
if(tempA != tempB) {
intersectionNode = tempA->next;
} else { // 2. A和B所有节点都是相同的，也就是栈A和栈B同时为空
intersectionNode = tempA;
}
return intersectionNode;
}
};
（3）方法三： 还有没有其他的数据结构能用呢？Hash表和集合？
可以，只将一个链表中的节点存到hash表或者集合中，然后遍历另外一个链表，看有没有集合中有没有一样的节点。
时间复杂度为O(n)，空间复杂度为O(n)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
set<ListNode*> setA;
while(headA != nullptr) {
setA.insert(headA);
headA = headA->next;
}
while (headB != nullptr) {
if (setA.find(headB) != setA.end()) {
return headB;
}
headB = headB->next;
}
return nullptr;
}
};
那还有没有时间或者空间复杂度更低的方法呢？一般这个时候，想要的方法都是稍微带一点技巧性了，多刷题的重要性在此时此刻就体现出来了。
（4）方法四： 拼接法，既然两个链表最后的部分都是一样的。那我们将两个链表拼一下，就像A和B，我们拼成AB和BA两种，然后进行遍历，最后肯定会在某一个节点达成相同的。
注意，我们是为了减少空间复杂度来跟进一步地找方法的，如果我们又去新建两个链表岂不是违背初衷了嘛？
那我们怎么办呢？
欸，我们只需要在遍历完A后，接着遍历B，不就组成AB了。同样遍历B，再遍历A，就组成BA了。而且，一边遍历一边比较，这样就OK啦！
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode* pA = headA;
ListNode* pB = headB;
// 当不为公共节点时，就接着往下遍历
while (pA != pB) {
pA = pA->next;
pB = pB->next;
/* 考虑边界条件，那就是没有公共节点的时候
* 在更新pA和pB之后，如果pA == pB == nullptr
* 就意味着AB和BA对比完了，那我们就不能继续下去
* 否则会导致ABABABAB……和BABABABA……无限下去造成死循环了
* */
if (pA != pB) {
// 拼成AB，当A遍历完了，就接着遍历B
if (pA == nullptr) {
pA = headB;
}
// 拼成BA，当B遍历完了，就接着遍历A
if (pB == nullptr) {
pB = headA;
}
}
}
return pA;
}
};
（5）方法五： 对于链表而言，我们最常用的方法还有一个双指针的方法。
既然两个链表尾巴部分一样，那就两个指针一起开始遍历嘛，如果同时遍历到同一个节点，那不就是我们要找的第一个公共节点嘛。
但是要是像图中这样去遍历，因为A和B长度不一样，那pA和pB永远都不可能遍历到同一个节点上嘛！
这个简单啊，我们让他们从同一起点出发不就好了，谁的跑道长，那我们就先让谁先跑一点，保证两个指针在同一起跑线就好啦！文章来源：https://www.toymoban.com/news/detail-603242.html
文章来源地址https://www.toymoban.com/news/detail-603242.html
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 遍历A，得到A的长度
ListNode *pA = headA;
int lengthA = 0;
while(pA != nullptr) {
++lengthA;
pA = pA->next;
}
// 遍历B，得到B的长度
ListNode *pB = headB;
int lengthB = 0;
while(pB != nullptr) {
++lengthB;
pB = pB->next;
}
pA = headA;
pB = headB;
// 计算长度差并统一起跑点
if(lengthA - lengthB > 0) {
int sub = lengthA - lengthB;
while(sub != 0) {
pA = pA->next;
--sub;
}
} else if (lengthB - lengthA > 0) {
int sub = lengthB - lengthA;
while(sub != 0) {
pB = pB->next;
--sub;
}
}
while(pA != nullptr && pB != nullptr) {
if (pA == pB) {
break;
}
pA = pA->next;
pB = pB->next;
}
return pA;
}
};
到了这里，关于算法通关村第一关——链表经典问题之第一个公共子节点笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
