C++ 求两个链表的公共结点
翟天保Steven 人气:0题目描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： n<=1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例：
输入：
{1,2,3},{4,5},{6,7}
返回值：
{6,7}
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
解题思路：
本题考察数据结构链表的使用。将两个链表指针向前步进，走到头后就错位继续前进，因为两个指针行进的速度一致，走着走着就撞一起了，如下方gif动画所示，很直观。
测试代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *a=pHead1,*b=pHead2;
while(a!=b)
{
a=a?a->next:pHead2;
b=b?b->next:pHead1;
}
return a;
}
};
补充
通过C++找出两个链表的所有公共结点：
// FindFirstCommandNode.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
ListNode(int i):m_nKey(i)
{
}
};
//获取链表长度
int GetListLength(ListNode* pHead)
{
int nLength = 0;
ListNode* pNode = pHead;
while (pNode != NULL)
{
++nLength;
pNode = pNode->m_pNext;
}
return nLength;
}
ListNode* FindFirstCommandNode(ListNode* pHead1, ListNode* pHead2)
{
int nLength1 = GetListLength(pHead1);
int nLength2 = GetListLength(pHead2);
int nLengthDif = 0;//两个链表的长度差
ListNode* pListHeadLong = NULL;//用于指向长链表
ListNode* pListHeadShort = NULL;//用于指向短链表
//根据长度判断 链表指向
if (nLength1 > nLength2)
{
nLengthDif = nLength1 - nLength2;
pListHeadShort = pHead2;
pListHeadLong = pHead1;
}
else
{
nLengthDif = nLength2 - nLength1;
pListHeadLong = pHead2;
pListHeadShort = pHead1;
}
//先对长链表进行移动 移动到与短链表长度相同的位置
for (int i = 0; i < nLengthDif; i++)
{
pListHeadLong = pListHeadLong->m_pNext;
}
//寻找公共节点
while (pListHeadLong !=NULL && pListHeadShort != NULL && pListHeadLong!= pListHeadShort)
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}
//如果不为空 此时的pListHeadLong 与pListNodeShort为同一个节点，返回该节点
if (pListHeadLong != NULL)
{
return pListHeadLong;
}
else
{
return NULL;//否则返回NULL
}
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode* head1 = new ListNode(0);
ListNode* head2 = new ListNode(1);
ListNode* node0 = new ListNode(22);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
ListNode* node5 = new ListNode(6);
ListNode* node6 = new ListNode(7);
ListNode* node8 = new ListNode(6);
head1->m_pNext = node1;
node1->m_pNext = node0;
node0->m_pNext = node3;
node3->m_pNext = node5;
node5->m_pNext = node6;
node6->m_pNext = NULL;
head2->m_pNext = node2;
node2->m_pNext = node4;
node4->m_pNext = node8;
node8->m_pNext = node6;
node6->m_pNext = NULL;
cout<<"链表1的长度为："<<GetListLength(head1)<<endl;
cout<<"链表2的长度为："<<GetListLength(head2)<<endl;
ListNode* CommNode = FindFirstCommandNode(head1,head2);
if (CommNode!= NULL)
{
cout<<"公共节点的值为："<<CommNode->m_nKey<<endl;
}
else
{
cout<<"没有公共节点"<<endl;
}
getchar();
return 0;
}
加载全部内容