剑指offer36:两个链表的第一个公共结点
阅读原文时间:2023年07月09日阅读:4

1 题目描述

  输入两个链表,找出它们的第一个公共结点。

2 思路和方法

  方法一:

  用两个指针同时从两个链表的表头开始走,当走到自己的链表结尾的时候开始从另一个链表的表头开始向后走。终止条件就是两个指针第一次相遇。此时指针位置即为所求。(两个链表的节点和是一定的,所以两个指针一定可以同时遍历完两条链表,即在最后时刻两个指针一定是重合的)

  方法2:

  先数出两条链表的长度,得到长度差d,先将长链表从头结点往后走d步,之后第二个链表从头开始,两个链表一起一步一步走,直到两个链表的节点第一次相等为止,此时指针位置即为所求。

3 C++核心代码

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
ListNode *p1 = pHead1;
ListNode *p2 = pHead2;
while(p1!=p2){
p1 = (p1==NULL ? pHead2 : p1->next);
p2 = (p2==NULL ? pHead1 : p2->next);
}
return p1;
}

 ListNode\* FindFirstCommonNode( ListNode\* pHead1, ListNode\* pHead2) {  
     ListNode \*p1=pHead1;  
     ListNode \*p2=pHead2;  
     int len1=,len2=,diff=;  
     while(p1!=NULL){  
         p1=p1->next;  
         len1++;  
     }  
     while(p2!=NULL){  
         p2=p2->next;  
         len2++;  
     }  
     if(len1>len2){  
         diff=len1-len2;  
         p1=pHead1;  
         p2=pHead2;  
     }  
     else{  
         diff=len2-len1;  
         p1=pHead2;  
         p2=pHead1;  
     }  
     for(int i=;i<diff;i++){  
         p1=p1->next;  
     }  
     while(p1!=NULL && p2!=NULL){  
         if(p1==p2)  
             break;  
         p1=p1->next;  
         p2=p2->next;  
     }  
     return p1;  
 }

4 C++完整代码

#include
using namespace std;

struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};

//创建链表节点
ListNode* CreateListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pNext = NULL;

 return pNode;  

}

//连接链表节点
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
if (pCurrent == NULL)
{
//exit(1),非正常运行导致退出程序;exit(0),正常运行并退出程序
cout << "Error to connect two nodes." << endl;
exit();
}

 pCurrent->m\_pNext = pNext;  

}

//销毁链表
void DestroyList(ListNode* pHead)
{
ListNode* pNode = pHead;

 while (pNode!=NULL)  
 {  
     pHead = pHead->m\_pNext;  
     delete pNode;  
     pNode = pHead;  
 }  

}

//销毁节点
void DestroyNode(ListNode* pNode)
{
delete pNode;
pNode = NULL;
}

//求链表的长度
unsigned int GetListLength(ListNode* pHead)
{
unsigned int nLength = ;
ListNode* pNode = pHead;

 while (pNode!=NULL)  
 {  
     nLength++;  
     pNode = pNode->m\_pNext;  
 }

 return nLength;  

}

//找第一个公共节点
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2)
{
//求两个链表的长度
unsigned int nLength1 = GetListLength(pHead1);
unsigned int nLength2 = GetListLength(pHead2);
//两个链表的长度差
int nLengthDif = nLength1 - nLength2;
ListNode* pListHeadLong = pHead1;
ListNode* pListHeadShort= pHead2;
if (nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}

 // 先在长链表上走几步,再同时在两个链表上遍历  
 for (int i = ; i < nLengthDif; i++)  
 {  
     pListHeadLong = pListHeadLong->m\_pNext;  
 }

 while ((pListHeadLong!=NULL)&& (pListHeadShort != NULL)&&(pListHeadLong != pListHeadShort))  
 {  
     pListHeadLong = pListHeadLong->m\_pNext;  
     pListHeadShort = pListHeadShort->m\_pNext;  
 }

 //得到第一个公共节点  
 ListNode\* pFisrtCommonNode = pListHeadLong;  
 //ListNode\* pFisrtCommonNode = pListHeadShort;也可以

 return pFisrtCommonNode;  

}

// ====================测试代码====================
void Test(char* testName, ListNode* pHead1, ListNode* pHead2, ListNode* pExpected)
{
if (testName != NULL)
{
cout << testName << " begins: ";
}

 ListNode\* pResult = FindFirstCommonNode(pHead1, pHead2);  
 if (pResult == pExpected)  
 {  
     cout << "Succeed!" << endl;  
 }  
 else  
 {  
     cout << "Failed!" << endl;  
 }  

}

// 第一个公共结点在链表中间
// 1 - 2 - 3 \
// 6 - 7
// 4 - 5 /
void Test1()
{
ListNode* pNode1 = CreateListNode();
ListNode* pNode2 = CreateListNode();
ListNode* pNode3 = CreateListNode();
ListNode* pNode4 = CreateListNode();
ListNode* pNode5 = CreateListNode();
ListNode* pNode6 = CreateListNode();
ListNode* pNode7 = CreateListNode();

 ConnectListNodes(pNode1, pNode2);  
 ConnectListNodes(pNode2, pNode3);  
 ConnectListNodes(pNode3, pNode6);  
 ConnectListNodes(pNode4, pNode5);  
 ConnectListNodes(pNode5, pNode6);  
 ConnectListNodes(pNode6, pNode7);

 Test("Test1", pNode1, pNode4, pNode6);

 DestroyNode(pNode1);  
 DestroyNode(pNode2);  
 DestroyNode(pNode3);  
 DestroyNode(pNode4);  
 DestroyNode(pNode5);  
 DestroyNode(pNode6);  
 DestroyNode(pNode7);  

}

// 没有公共结点
// 1 - 2 - 3 - 4
//
// 5 - 6 - 7
void Test2()
{
ListNode* pNode1 = CreateListNode();
ListNode* pNode2 = CreateListNode();
ListNode* pNode3 = CreateListNode();
ListNode* pNode4 = CreateListNode();
ListNode* pNode5 = CreateListNode();
ListNode* pNode6 = CreateListNode();
ListNode* pNode7 = CreateListNode();

 ConnectListNodes(pNode1, pNode2);  
 ConnectListNodes(pNode2, pNode3);  
 ConnectListNodes(pNode3, pNode4);  
 ConnectListNodes(pNode5, pNode6);  
 ConnectListNodes(pNode6, pNode7);

 Test("Test2", pNode1, pNode5, NULL);

 DestroyList(pNode1);  
 DestroyList(pNode5);  

}

// 公共结点是最后一个结点
// 1 - 2 - 3 - 4 \
// 7
// 5 - 6 /
void Test3()
{
ListNode* pNode1 = CreateListNode();
ListNode* pNode2 = CreateListNode();
ListNode* pNode3 = CreateListNode();
ListNode* pNode4 = CreateListNode();
ListNode* pNode5 = CreateListNode();
ListNode* pNode6 = CreateListNode();
ListNode* pNode7 = CreateListNode();

 ConnectListNodes(pNode1, pNode2);  
 ConnectListNodes(pNode2, pNode3);  
 ConnectListNodes(pNode3, pNode4);  
 ConnectListNodes(pNode4, pNode7);  
 ConnectListNodes(pNode5, pNode6);  
 ConnectListNodes(pNode6, pNode7);

 Test("Test3", pNode1, pNode5, pNode7);

 DestroyNode(pNode1);  
 DestroyNode(pNode2);  
 DestroyNode(pNode3);  
 DestroyNode(pNode4);  
 DestroyNode(pNode5);  
 DestroyNode(pNode6);  
 DestroyNode(pNode7);  

}

// 公共结点是第一个结点
// 1 - 2 - 3 - 4 - 5
// 两个链表完全重合
void Test4()
{
ListNode* pNode1 = CreateListNode();
ListNode* pNode2 = CreateListNode();
ListNode* pNode3 = CreateListNode();
ListNode* pNode4 = CreateListNode();
ListNode* pNode5 = CreateListNode();

 ConnectListNodes(pNode1, pNode2);  
 ConnectListNodes(pNode2, pNode3);  
 ConnectListNodes(pNode3, pNode4);  
 ConnectListNodes(pNode4, pNode5);

 Test("Test4", pNode1, pNode1, pNode1);

 DestroyList(pNode1);  

}

// 输入的两个链表有一个空链表
void Test5()
{
ListNode* pNode1 = CreateListNode();
ListNode* pNode2 = CreateListNode();
ListNode* pNode3 = CreateListNode();
ListNode* pNode4 = CreateListNode();
ListNode* pNode5 = CreateListNode();

 ConnectListNodes(pNode1, pNode2);  
 ConnectListNodes(pNode2, pNode3);  
 ConnectListNodes(pNode3, pNode4);  
 ConnectListNodes(pNode4, pNode5);

 Test("Test5", NULL, pNode1, NULL);

 DestroyList(pNode1);  

}

// 输入的两个链表都是空链表
void Test6()
{
Test("Test6", NULL, NULL, NULL);
}

int main()
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
system("pause");
return ;
}

参考资料

https://blog.csdn.net/lingfeng2019/article/details/80778598

https://blog.csdn.net/yanxiaolx/article/category/6250534(完整代码)

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章