题目：输入两个链表，找出它们的第一个公共子节点。

直观做法：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，说明两个链表在这个节点上重合，于是就找到了它们的公共节点。如果第一个链表的长度为 m， 第二个链表的长度为 n，显然，该方法的时间复杂度是 O(mn)。

    分析有公共节点的两个链表的特点：如果两个单向链表有公共节点，那么这两个链表从某个公共的节点开始，它们的 pNext 指针都指向同一个节点。由于是单向链表的节点，每个节点只有一个 pNext，因此，从第一个公共节点开始，之后它们所有的节点都是重合的没有分叉。拓扑形状看起来像一个 Y，而不可能像一个 X。

（一） 如果两个链表有公共节点，那么公共节点出现在两个链表的尾部。如果从两个链表的尾部开始往前比较，最后一个相同的节点就是要找的节点。问题是在单向链表中，只能从头结点开始按顺序遍历，最后才能到达尾节点。最后到达的尾节点却要最先比较，可以想到使用栈的特点来解决这个问题：分别把两个链表的节点放到两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出，接着比较下一个栈顶，直到找到最后一个相同的节点。

    上述思路需要两个辅助栈，如果连表的长度分别为 m 和 n， 那么空间复杂度为 O(m+n)。这种思路的时间复杂度为 O(m+n)。

（二） 当两个链表的长度不相同时，如果从头开始遍历到达尾节点的时间就不一致。解决这一问题还有一个更简单的方法：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着在同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。时间复杂度为 O(m+n)。

//两个链表的第一个公共节点
#include<iostream>
using namespace std;

typedef int ElemType;
typedef struct LNode
{
 ElemType data;
 struct LNode *pNext;
}ListNode, *LinkList;

//获取链表长度
int GetListLength(LinkList pHead)
{
 if(pHead == NULL)
  return -1;
 int length = 0;
 ListNode *pNode = pHead->pNext;
 while(pNode != NULL)
 {
  length++;
  pNode = pNode->pNext;
 }
 return length;
}

ListNode* FindFistCommonNode(LinkList pHead1, LinkList pHead2)
{
 int length1 = GetListLength(pHead1);
 int length2 = GetListLength(pHead2);
 int lengthDiff = length1 - length2;
 
 ListNode *pListLong = pHead1->pNext;
 ListNode *pListShort = pHead2->pNext;
 if(length1 < length2)
 {
  pListLong = pHead2->pNext;
  pListShort = pHead1->pNext;
  lengthDiff = length2 - length1;
 }
 //将指向较长的链表的指针后移，使其剩余的节点与较短链表的数目相同
 for(int i = 0; i < lengthDiff; i++)
 {
  pListLong = pListLong->pNext;
 }
 //开始同步移动，找到第一个相同的节点
 while(pListLong != NULL && pListShort != NULL && pListLong != pListShort )
 {
  pListLong = pListLong->pNext;
  pListShort = pListShort->pNext;
 }
 //返回结点指针
 ListNode *firstCommonNode = pListLong;
 return firstCommonNode;
}

void PrintLinkList(ListNode *L)
{
 if(L == NULL)
  return;
 ListNode *pNode = L->pNext;
 while(pNode != NULL)
 {
  cout << pNode->data << " ";
  pNode = pNode->pNext;
 }
 cout << endl;
}

//创建两个含有公共节点的链表（带有头节点）
void InsertLinkList(ListNode *L, int value)
{
 if(L == NULL)
  return;

 ListNode *tempNode = L;
 while(tempNode->pNext != NULL)
  tempNode = tempNode->pNext;
 ListNode* pNode = new ListNode();
 pNode->data = http://www.mamicode.com/value;
 pNode->pNext = tempNode->pNext;
 tempNode->pNext = pNode;
}
void CreateTwoLinkList(ListNode *L1, ListNode *L2)
{
 ListNode *L3 = new ListNode();
 L3->pNext = NULL;
 for(int i = 1; i < 4; i++)
 {
  InsertLinkList(L1, i);
 }
 for(int i = 6; i < 8; i++)
  InsertLinkList(L3, i);

 ListNode *pNode = L1;
 while(pNode->pNext != NULL)
  pNode = pNode->pNext;
 pNode->pNext = L3->pNext;

 for(int i = 4; i < 6; i++)
 {
  InsertLinkList(L2, i);
 }

 pNode = L2;
 while(pNode->pNext != NULL)
  pNode = pNode->pNext;
 pNode->pNext = L3->pNext;

 delete L3;
 L3 = NULL;
}

int main()
{
 ListNode *L1 = new ListNode();
 L1->pNext = NULL;
 ListNode *L2 = new ListNode();
 L2->pNext = NULL;
 CreateTwoLinkList(L1, L2);

 PrintLinkList(L1);
 PrintLinkList(L2);

 ListNode *commonNode = NULL;
 commonNode = FindFistCommonNode(L1, L2);
 cout << commonNode->data << endl;

 system("pause");
 return 0;
}

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