链表练习题c++代码实现(二)：寻找两条单链表的公共结点

链表练习题c++代码实现(二)：寻找两条单链表的公共结点 寻找条链表的公共结点

• 若两条链表有公共结点，则这两条链表和公共结点的样子应该是Y形状的
• 两条链表可能不等长，所以长链表要先进行遍历，等遍历到剩余结点和短链表一样时再共同往后走，进行比较
• 本代码所建立的链表都是带头结点的，采用面向对象实现

lscc.h文件
对方法的声明在这个文件里，具体实现在lscc.cpp文件后文有

#ifndef LSCC_H
#define LSCC_H
#include 

using namespace std;

//定义链表中的数据结点
typedef struct ListNode{
    int data;//数据域
    ListNode *next;//指针域
}ListNode,*linkList;
//第一个listNode指的是一个结点
/
class lscc
{
    public:
        lscc();
        ~lscc();
        //定义：生成链表的函数
        //头插法：
        linkList List_HeadInsert();
        //尾插法:
        linkList List_TailInsert();

        //定义一个输出单链表的函数
        void printlink(linkList &);

        //计算链表的表长
        int Length(linkList &);
        
        //8.给定两个链表，找出两个链表的公共结点
        linkList search_1st_Common(linkList &, linkList &);


};

#endif // LSCC_H

lscc.cpp
函数的具体实现

//8.给定两个链表，找出两个链表的公共结点
linkList lscc::search_1st_Common(linkList &L, linkList &S) {
    
    int len1 = Length(L), len2 = Length(S);
    int dest;
    linkList longlist = new ListNode;
    linkList shortlist = new ListNode;//定义两个链表指针，随后分别指向长链表和短链表
    if (len1 < len2) {
        dest = len2 - len1;
        longlist = S->next;
        shortlist = L->next;
    } else {
        dest = len1 - len2;
        longlist = L->next;
        shortlist = S->next;
    }
    //让长列表先走dest个结点
    while (dest--) {
        longlist = longlist->next;
    }

    //现在开始共同遍历
    while (longlist != NULL) {
        //while后面写shortlist != NULL效果是一样的
        if ( longlist->next == shortlist->next) {
            //如果遍历过程中，两个链表相等了，则返回，这时候已经找到了
            return longlist;
        }
        else {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }

    return NULL;//如果最后还没找到，返回NULL，代表没有共同的结点

}

main.cpp文件

#include 
#include 
#include "sxcc_13.h"
#include "lscc.h"

using namespace std;

int main() {
	lscc list1;
    ListNode *L, *S, *a, *common;//a为一会要拼接在L和S后面的公共部分

    L = list1.List_TailInsert();//尾插法建立链表
    list1.printlink(L);//输出链表(检查下)
    cout << "链表L的表长是：" << list1.Length(L) << endl;
    
	S = list1.List_TailInsert();
    list1.printlink(S);
    cout << "链表S的表长是：" << list1.Length(S) << endl;
    
    a = list1.List_TailInsert();//这里先自己模拟一串公共结点，给L和S拼接上
    ListNode *r1, *r2;//两个结点的指针, r1,r2
    r1 = L;
    r2 = S;
    while (r1->next != NULL)
        r1 = r1->next;
    while (r2->next != NULL)
        r2 = r2->next;
    r1->next = a->next;
    r2->next = a->next;

    cout << "这是拼接过后的L" << endl;
    list1.printlink(L);
    cout << "这是拼接过后的S" << endl;
    list1.printlink(S);
//到这里拼接完成

//开始运行寻找公共结点的方法并打印
    cout << "使用search_1st_common寻找L和S的公共链表common" << endl;
    common = list1.search_1st_Common(L,S);
    cout << "链表common的表长是：" << list1.Length(common) << endl;
    cout << "输出打印公共链表"<< endl;
    list1.printlink(common);

}