两个链表第一个公共结点

题目：输入两个链表，找出它们的第一个公共节点。链表的定义如下：struct ListNode{int m_nValue;ListNode *m_pNext; };思路1：采用蛮力的方法：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果第二个链表上的节点和第一个链表上的节点一样，就说明两个链表在节点上重合，于是就找到了公共的节点。而通常蛮力并不是好的方法。思路2:首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，先在较长的节点上走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的公共的节点。#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
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）
{
printf（"Error to connect two nodes. "）;
exit（1）;
} pCurrent->m_pNext = pNext;
} void PrintListNode（ListNode* pNode）
{
if（pNode == NULL）
{
printf（"The node is NULL "）;
}
else
{
printf（"The key in node is %d. ", pNode->m_nValue）;
}
} void PrintList（ListNode* pHead）
{
printf（"PrintList starts. "）; ListNode* pNode = pHead;
while（pNode ！= NULL）
{
printf（"%d ", pNode->m_nValue）;
pNode = pNode->m_pNext;
} printf（" PrintList end. "）;
}void DestroyList（ListNode* pHead）
{
ListNode* pNode = pHead;
while（pNode ！= NULL）
{
pHead = pHead->m_pNext;
delete pNode;
pNode = pHead;
}
}unsigned int GetListLength（ListNode* pHead）;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 = 0; 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;

return pFisrtCommonNode;
}unsigned int GetListLength（ListNode* pHead）
{
unsigned int nLength = 0;
ListNode* pNode = pHead;
while（pNode ！= NULL）
{
++ nLength;
pNode = pNode->m_pNext;
}

return nLength;
}// 第一个公共结点在链表中间
// 1 - 2 - 3
// 6 - 7
// 4 - 5 /
int main（）
{
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）; ListNode* pResult = FindFirstCommonNode（pNode1, pNode4）;
printf（"%d ",pResult->m_nValue）;

DestroyNode（pNode1）;
DestroyNode（pNode2）;
DestroyNode（pNode3）;
DestroyNode（pNode4）;
DestroyNode（pNode5）;
DestroyNode（pNode6）;
DestroyNode（pNode7）;

return 0;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/132843.htm