剑指offer37-两个链表的第一个公共节点

//输入两个链表，找出他们的第一个公共节点 //最原始的方法是以其中一个链表最为大循环，对于每一个节点在另一个链表中寻找是否有相同节点 /*方法一****/ //如果同时从尾部开始访问的话，则只要找到第一个不同的节点就可以，因为其前一个节点就是从头访问的第一个共同节点 //但是链表只能从头开始访问，而从头访问的话，两条链表到达公共节点的时间点是不一致的 //而根据两天链表的特点，由于二者在第一个公共节点之后都是相同的 //那么对于其差别，则是在第一个公共节点之前部分，也就是二者如果长度不一样的话，只能在前面部分 //而如果要同时到达公共节点的话，需要从距第一个公共节点相同距离的地方开始共同向后访问 //因而，可以先获取两条链表的长度，然后得到其长度差，让更长的链表先“空转”该长度， //然后在开始两个链表共同向后访问，并比较其节点是否相同，知道找到第一个共同节点

#include <iostream> #include "../Utilties/List.h" #include <stack> using namespace std; ListNode* FirstCommonNode_Solution1(ListNode* pHead1, ListNode* pHead2) { if (pHead1==NULL||pHead2==NULL) { return NULL; } int Len1 = 0; int Len2 = 0; int DiffLen = 0; ListNode* pNode1 = pHead1; ListNode* pNode2 = pHead2; while (pNode1!=NULL) { Len1++; pNode1 = pNode1->m_pNext; } while (pNode2!=NULL) { Len2++; pNode2 = pNode2->m_pNext; } if (Len1>Len2) //pNode1始终指向更长的那个 { pNode1 = pHead1; pNode2 = pHead2; DiffLen = Len1 - Len2; } else { pNode2 = pHead1; pNode1 = pHead2; DiffLen = Len2 - Len1; } while (DiffLen>0) { pNode1 = pNode1->m_pNext; DiffLen--; } while (pNode1!=NULL && pNode2!=NULL && pNode1!=pNode2) { pNode1=pNode1->m_pNext; pNode2=pNode2->m_pNext; } if (pNode1==NULL) { return NULL; } else { return pNode1; } }

//**********方法二****/ 根据之前的描述，如果从尾部开始访问的话，由于第一个公共节点后，两条链表是相同的,因而可以很容易得到二者的第一个非公共节点,在得到第一个非公共节点之前则是从后往前的最后一个公共节点，也就是从前往后的第一个公共节点.而从后往前访问，则可以通过栈来实现。定义两个栈，首先分别将两个链表的各个节点分别入栈，然后同时从栈中推出元素，直至栈顶元素不一致为止。

ListNode* FirstCommonNode_Solution2(ListNode* pHead1, ListNode* pHead2) { if (pHead1 == NULL || pHead2 == NULL) { return NULL; } ListNode* FirstCommonNode = NULL; ListNode* pNode1 = pHead1; ListNode* pNode2 = pHead2; stack<ListNode*> NodeStack1; stack<ListNode*> NodeStack2; while (pNode1!=NULL) { NodeStack1.push(pNode1); pNode1 = pNode1->m_pNext; } while (pNode2!=NULL) { NodeStack2.push(pNode2); pNode2 = pNode2->m_pNext; } //while (!NodeStack1.empty() && !NodeStack2.empty()) //{ // if (NodeStack1.top()==NodeStack2.top()) // { // NodeStack1.pop(); // NodeStack2.pop(); // } // else // { // return NodeStack1.top()->m_pNext; // } //} //之前使用上面的方案如果遇到两个链表完全相同的情况会出问题 //因为两个链表完全相同的时候，最后栈顶是没有元素的，所以也就不存在m_pNext,改成下面的 while (!NodeStack1.empty() && !NodeStack2.empty() && NodeStack1.top()==NodeStack2.top()) { FirstCommonNode = NodeStack1.top(); NodeStack1.pop(); NodeStack2.pop(); } return FirstCommonNode; }

// ==书中测试代码======

void DestroyNode(ListNode* pNode); void Test(char* testName, ListNode* pHead1, ListNode* pHead2, ListNode* pExpected) { printf("Solution1:\n"); if (testName != NULL) printf("%s begins: ", testName); ListNode* pResult = FirstCommonNode_Solution1(pHead1, pHead2); if (pResult == pExpected) printf("Passed.\n"); else printf("Failed.\n"); printf("Solution2:\n"); if (testName != NULL) printf("%s begins: ", testName); pResult = FirstCommonNode_Solution2(pHead1, pHead2); if (pResult == pExpected) printf("Passed.\n"); else printf("Failed.\n"); } // 第一个公共结点在链表中间 // 1 - 2 - 3 \ // 6 - 7 // 4 - 5 / void Test1() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ListNode* pNode6 = CreateListNode(6); ListNode* pNode7 = CreateListNode(7); 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(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ListNode* pNode6 = CreateListNode(6); ListNode* pNode7 = CreateListNode(7); 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(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ListNode* pNode6 = CreateListNode(6); ListNode* pNode7 = CreateListNode(7); 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(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); Test("Test4", pNode1, pNode1, pNode1); DestroyList(pNode1); } // 输入的两个链表有一个空链表 void Test5() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); 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); } void DestroyNode(ListNode* pNode) { delete pNode; pNode = NULL; } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; }