《剑指offer》第五十二题（两个链表的第一个公共结点）

// 面试题52：两个链表的第一个公共结点// 题目：输入两个链表，找出它们的第一个公共结点。#include <iostream>#include“List.h”unsignedintGetListLength(ListNode* pHead);//下面这个时间复杂度是O（m+n），且不用辅助空间//另一种方法是使用两个栈，从尾到头比较，这样时间复杂度不变，空间复杂度O（m+n）ListNode*FindFirstCommonNode(ListNode*pHead1,ListNode*pHead2){// 得到两个链表的长度unsignedint nLength1 =GetListLength(pHead1);unsignedint nLength2 =GetListLength(pHead2);int nLengthDif = nLength1 – nLength2;//先设链表1比链表2长，求长度差 ListNode* pListHeadLong = pHead1;ListNode*pListHeadShort= pHead2;if(nLength2 > nLength1)//万一链表2比链表1长，重设{ pListHeadLong = pHead2; pListHeadShort = pHead1; nLengthDif = nLength2 – nLength1;}// 先在长链表上走几步，再同时在两个链表上遍历for(int i =; i < nLengthDif;++i) pListHeadLong = pListHeadLong->m_pNext;while((pListHeadLong !=nullptr)&&(pListHeadShort !=nullptr)&&(pListHeadLong !=pListHeadShort))//找到第一个相等的节点{ pListHeadLong = pListHeadLong->m_pNext; pListHeadShort = pListHeadShort->m_pNext;}// 得到第一个公共结点ListNode* pFisrtCommonNode = pListHeadLong;return pFisrtCommonNode;}unsignedintGetListLength(ListNode* pHead)//得到链表的长度{unsignedint nLength =;ListNode* pNode = pHead;while(pNode !=nullptr){++nLength; pNode =pNode->m_pNext;}return nLength;}// ====================测试代码====================voidDestroyNode(ListNode* pNode);voidTest(constchar* testName,ListNode*pHead1,ListNode* pHead2,ListNode* pExpected){if(testName !=nullptr) printf(“%s begins: “, testName);ListNode* pResult =FindFirstCommonNode(pHead1, pHead2);if(pResult== pExpected) printf(“Passed.\n”);else printf(“Failed.\n”);}// 第一个公共结点在链表中间// 1 – 2 – 3 \// 6 – 7// 4 – 5 /voidTest1(){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 – 7voidTest2(){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,nullptr);DestroyList(pNode1);DestroyList(pNode5);}// 公共结点是最后一个结点// 1 – 2 – 3 – 4 \// 7// 5 – 6 /voidTest3(){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// 两个链表完全重合voidTest4(){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);}// 输入的两个链表有一个空链表voidTest5(){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”,nullptr, pNode1,nullptr);DestroyList(pNode1);}// 输入的两个链表有一个空链表voidTest6(){Test(“Test6”,nullptr,nullptr,nullptr);}voidDestroyNode(ListNode* pNode){delete pNode; pNode =nullptr;}int main(int argc,char* argv[]){Test1();Test2();Test3();Test4();Test5();Test6(); system(“pause”);return;}