当前位置 博文首页 > kbtx的博客：王道408 数据结构之 给定两个单链表，编写算法找出
所谓找出两个单链表的公共节点，就是将链表相交的部分的第一个节点找出来，此节点后的所有节点都是公共节点。
如图，链表A的5个节点分别为a1,a2,c1,c2,c3，链表B的6个节点分别为b1,b2,b3,c1,c2,c3（注意此处没有考虑虚拟头节点的存在）
显然，从c1开始它们便不可能再出现分支，我们的算法也应当返回c1的地址。
当A、B的长度相同时，找出c1非常简单，只要我们设置两个指针curA, curB同时指向A、B的第一个数据节点，并依次比较两个指针指向的地址值是否相同，最终一定会在c1处返回。
但是，如果A、B长度不等，就没有这么简单了，curA和curB不会同时经过c1，自然无法在此处判断相等
解决方法倒是很简单，我们让curA和curB遍历完自己的链表后立刻遍历对方的，这样，就能强行令两个链表长度“相等”，因为在此时两个链表的组成部分分别是 A：蓝色->红色->黄色->红色；B：黄色->红色->蓝色->红色。其中最后一段红色就是公共部分，同一颜色长度相等，可见最后一段红色之前的长度一定时相等的，由此就将情况进行了化简。
下面开始用C++实现本算法，首先我们定义一个带头节点的链表，并定义相关操作：
typedef struct linkedList{
int data;
linkedList* next;
//构造函数
linkedList(){
//我们拿头节点的data域存储指向链表末尾的指针
printf("链表头节点已创建\n");
data = 0;
next = 0;
}
//析构函数，只要在栈空间创建头节点就无需担心内存泄漏问题
~linkedList(){
int i = 0;
linkedList* p = next;
while(p!=0){
linkedList* q = p->next;
free(p);
p = q;
++i;
}
printf("删除了%d个节点\n",i);
}
/**
*从当前节点开始输出后续的所有内容
**/
void output(){
linkedList* n = this;
//printf("%d -> ",data);
while(n->next != 0){
n = n->next;
printf("%d -> ",n->data);
}
printf("null\n");
}
/**
* 尾插法，将另一节点插入此链表末端，时间复杂度O(n)，可以优化为O(1)
**/
void insert_back(int value){
//假定当前给出的节点是头节点
linkedList* newNode = this->data==0?this: (linkedList*)this->data;
//printf("%d", newNode);
while(newNode->next != 0) newNode = newNode->next;
newNode->next = (linkedList*)malloc(sizeof(linkedList));
//记录当前末尾节点的位置
this->data = (int) newNode->next;
newNode->next->next = 0;
newNode->next->data = value;
}
/**
* 尾插法，将另一段链表插入此链表末端，时间复杂度O(n)
* 本方法比较危险，如需调用请务必将析构函数注释掉
**/
void insert_back(linkedList& nextList){
linkedList* lastNode = 0;
if(this->data!=0){
lastNode = (linkedList*)this->data;
} else {
lastNode = this;
}
while(lastNode->next!=0) lastNode = lastNode->next;
//linkedList的头节点不参与拼接过程
lastNode->next = nextList.next;
//现在可以遍历挂接链表了
while(lastNode->next!=0) lastNode = lastNode->next;
this->data = (int) lastNode;
}
/**
* 头插法，将新节点插入链表虚拟头节点之后，时间复杂度O(1)
**/
void insert_head(int value){
linkedList* dummyHead = this;
linkedList* newNode = (linkedList*)malloc(sizeof(linkedList));
newNode->next = this->next;
dummyHead->next = newNode;
newNode->data = value;
}
/**
*找出链表的公共节点
*/
linkedList* publicNode(linkedList* that){
linkedList* curA = this->next;
linkedList* curB = that->next;
while(curA!=curB){
//输出信息之前务必判断节点是否为空，避免崩溃
if(curA!=0&&curB!=0) printf("%d(%d) -- %d(%d)\n",curA->data,curA,curB->data,curB);
curA = (curA!=0)?curA->next:that->next;
curB = (curB!=0)?curB->next:this->next;
//getchar();
}
if(curA!=0&&curB!=0) printf("%d(%d) -- %d(%d)\n",curA->data,curA,curB->data,curB);
return curA;
}
} LinkList, *Node;
有了以上的基本方法，我们就可以写主函数运行算法了，当然，强烈建议把析构函数先给我注释掉，因为我并没有考虑double free的问题，可能会导致程序崩溃或陷入死循环。
int main(){
LinkList A,B,C;
//创建链表A、B、C，令A、B的节点数不相同
for(int i=0;i<2;i++){
A.insert_back(i+1);
}
for(int i=0;i<3;i++){
B.insert_back(i+10);
C.insert_back(i+100);
}
A.output();
B.output();
C.output();
//将C挂在A、B之后,此时构造出了我们需要的链表，如果调用了此方法，强烈建议将析构函数注释掉！！！
A.insert_back(C);
B.insert_back(C);
A.output();
B.output();
Node c1 = A.publicNode(&B);
printf("在(%d)处找到公共节点，节点值：%d",c1,c1->data);
}
说明：本案例在Code::Blocks 17.12上编译通过。
直接复制粘贴即可使用
typedef struct linkedList{
int data;
linkedList* next;
//构造函数
linkedList(){
//我们拿头节点的data域存储指向链表末尾的指针
printf("链表头节点已创建\n");
data = 0;
next = 0;
}
//析构函数，只要在栈空间创建头节点就无需担心内存泄漏问题
/*
~linkedList(){
int i = 0;
linkedList* p = next;
while(p!=0){
linkedList* q = p->next;
free(p);
p = q;
++i;
}
printf("删除了%d个节点\n",i);
}
*/
/**
*从当前节点开始输出后续的所有内容
**/
void output(){
linkedList* n = this;
//printf("%d -> ",data);
while(n->next != 0){
n = n->next;
printf("%d -> ",n->data);
}
printf("null\n");
}
/**
* 尾插法，将另一节点插入此链表末端，时间复杂度O(n)，可以优化为O(1)
**/
void insert_back(int value){
//假定当前给出的节点是头节点
linkedList* newNode = this->data==0?this: (linkedList*)this->data;
//printf("%d", newNode);
while(newNode->next != 0) newNode = newNode->next;
newNode->next = (linkedList*)malloc(sizeof(linkedList));
//记录当前末尾节点的位置
this->data =
