链表的第一个公共节点,链表的公共结点概念
BM10两个链表的第一个公共节点
知识点链表
描述两个无环单向链表，找到它们的第一个公共节点，如果没有公共节点则返回null。(注意，因为传入数据是链表，所以错误测试数据的提示以其他方式显示，以确保传入数据是正确的)
数据范围：
需求：空间复杂度，时间复杂度
例如，当您输入{1，2，3}、{4，5}、{6，7}时，两个非循环单向链表的结构如下图所示：
您可以看到它们的第一个公共节点的节点值为6，因此返回节点值为6的节点。
输入描述：输入分为三段，第一段是第一链表的非公开部分，第二段是第二链表的非公开部分，第三段是第一链表和第二链表的公开部分。后台会把这三个参数组装成两个链表，这两个链表对应的头节点会传入函数FindFirstCommonNode，用户得到的只是pHead1和pHead2。
返回值说明：返回传入的pHead1和pHead2的第一个公共节点，后台会打印以该节点为头节点的链表。
示例1输入：
{1，2，3}，{4，5}，{6，7}复制返回值：
{6，7}复制说明：
第一个参数{1，2，3}表示第一个链表的非公开部分，第二个参数{4，5}表示第二个链表的非公开部分，最后一个参数{6，7}表示两个链表的公开部分。
这三个参数最后在后台组装成两个无环的单链表，它们是例2的输入，有共同的节点：
{1}，{2，3}，{0}复制返回值：
{}副本描述：
两个链表没有公共节点，返回null，后台打印{0}个问题解。方法1在set的帮助下遍历链表。
#包含位/标准数据。h
结构列表节点
{
int val
struct ListNode * next
ListNode(int x) : val(x)，next(nullptr)
{
}
ListNode()=默认值；
};
ListNode * FindFirstCommonNode(ListNode * phead 1，ListNode *pHead2)
{
STD:unordered _ set ListNode * s；
while (pHead1！=nullptr)
{
s . insert(phead 1)；
phead 1=phead 1-next；
}
while (pHead2！=nullptr)
{
if (s.find(pHead2)！=s.end())
{
返回pHead2
}
phead 2=phead 2-next；
}
返回nullptr
}
方法二：首先计算两个链表的长度，假设长度分别为n和m。让较长的链表先走n-m再同步走。当两个链表指向同一个节点时，就是我们要找的节点。
intlenth(listnode * phead){//计算链表长度的函数
ListNode * p=pHead
int n=0；
而(p！=NULL){
n；
p=p-next；
}
返回n；
}
ListNode * FindFirstCommonNode(ListNode * phead 1，ListNode* pHead2) {
int P1=list lenth(phead 1)；
int p2=list lenth(phead 2)；
If(p1=p2){ //当链表1较长时，链表1指针先走p1-p2步。
int n=P1-p2；
for(int I=0；I n；i ){
phead 1=phead 1-next；
}
而((pHead1！=NULL) (pHead2！=NULL) (pHead1！=pHead2)){ //两个链表同时移动，直到有一个公共节点时停止。
phead 1=phead 1-next；
phead 2=phead 2-next；
}
}
Else{ //反之，链表2先走p2-p1步。
int n=p2-P1；
for(int I=0；I n；i ){
phead 2=phead 2-next；
}
而((pHead1！=NULL) (pHead2！=NULL) (pHead1！=pHead2)){
phead 1=phead 1-next；
phead 2=phead 2-next；
}
}
返回pHead1
}
第三种方法是基于上述方法长度差的思想。不像上面提到的一个指针，只需要连接两个链表，同步两个指针。很容易将两个长度相等的链表连接在一起。对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分也是一样的，因为两个链表都走了，所以第一个相同的节点就是一圈后的第一个公共节点。
不需要将两个链表物理地连接在一起，当指针位于一个链表的末尾时，指针直接跳转到另一个链表的头部。具体例子请参考图示。
ListNode * FindFirstCommonNode(ListNode * phead 1，ListNode* pHead2)
{
如果(！pHead1 ！PHead2) //如果其中一个为空，则不能有公共节点，返回null
返回NULL
ListNode * p1=pHead1
ListNode * p2=pHead2
而(p1！=p2) //相当于遍历两个链表的所有值
{
p1=p1==NULL？phead 2:P1-next；
p2=p2==NULL？phead 1:p2-next；
}
返回P1；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。