两个链表的第一个公共节点

/********************************************************************
题目:输入两个链表，找出它们的第一个公共节点。
********************************************************************/
/*
解题思路：
先遍历两个链表得到他们的长度，就能知道哪个链表较长，以及长的链表比短的
链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同
时在两个链表上遍历，找到第一个相同的节点就是他们的第一个公共节点。
*/
#include
  
   
struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};
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* pLong = pHead1;
	ListNode* pShort = pHead2;
	
	if(nLength1 < nLength2)
	{
		pLong = pHead2;
		pShort = pHead1;
		nLengthDif = nLength2 - nLength1;
	}

	for(int i=0; i
   
    m_pNext; while((pLong != NULL) && (pShort != NULL) && (pLong != pShort)) { pLong = pLong->m_pNext; pShort = pShort->m_pNext; } //得到第一个公共节点 ListNode* pFirstCommonNode = pLong; return pFirstCommonNode; } int getListLength(ListNode* pHead) { if(pHead == NULL) return 0; unsigned int nLength = 0; ListNode* pNode = pHead; while(pNode != NULL) { ++nLength; pNode = pNode->





m_pNext; } return nLength; } ListNode* createListNode(int value) { ListNode* pNode = new ListNode(); pNode->m_nValue = value; pNode->m_pNext = NULL; return pNode; } void connect(ListNode* pNode1, ListNode* pNode2) { if(pNode1 == NULL || pNode2 == NULL) return; pNode1->m_pNext = pNode2; } void test() { ListNode* pNode1 = createListNode(1); ListNode* pNode2 = createListNode(2); ListNode* pNode3 = createListNode(3); ListNode* pNode4 = createListNode(4); ListNode* pNode5 = createListNode(6); ListNode* pNode6 = createListNode(7); connect(pNode1,pNode2); connect(pNode2,pNode3); connect(pNode3,pNode4); connect(pNode4,pNode5); connect(pNode5,pNode6); ListNode* pNode11 = createListNode(4); ListNode* pNode12 = createListNode(5); connect(pNode11,pNode12); connect(pNode12,pNode5); connect(pNode5,pNode6); ListNode* pFirst = findFirstCommonNode(pNode1,pNode11); if(pFirst != NULL) printf("%d\n",pFirst->m_nValue); } int main() { test(); return 0; }
   
  

时间复杂度为O(M+N)

==参考剑指offer