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

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

1struct node   

2{   

3   int v;   

4  node *next;   

5};  

面试这道题的时候很多的面试者第一反应就是采用蛮力的方法：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果第二个链表上的节点和第一个链表上的节点一样，就说明两个链表在节点上重合，于是就找到了公共的节点。而通常蛮力并不是好的方法。

从链表的定义可以看出，这两个链表是单链表，如果两个链表有公共节点，那么这两个链表从某一节点开始，它们的m_pNext都指向同一个节点，之后它们所有的节点都是重合的，不可能再出现分叉。所以拓扑形状看起来是Y型。

一个简单的方法是：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，先在较长的节点上走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的公共的节点。

具体实现的程序如下：

 

1struct node   

2{   

3   int v;   

4  node *next;   

5};   

6/*  

7返回链表的长度  

8链表为空 返回0  

9*/   

10size_t listLen(node * p)   

11{   

12    size_t num = 0;   

13    while (p!=NULL)   

14    {   

15        num++;   

16        p = p->next;   

17    }   

18    return num;   

19}   

20// 如果找到了 则返回指针 指向公共节点   

21// 如果不存在 则返回空指针   

22node * findFirstCommenNode(node * pheada, node * pheadb)   

23{   

24    size_t lenA = listLen(pheada);   

25    size_t lenB = listLen(pheadb);   

26     

27    node * plistA = pheada;   

28    node * plistB = pheadb;   

29    //调整长度   

30    //plistA 指向较长的一个   

31    if (lenA < lenB)   

32    {   

33        plistB = pheada;   

34        plistA = pheadb;   

35       size_t t = lenA;   

36        lenA = lenB;   

37        lenB = t;   

38    }   

39    while(lenA > lenB)   

40    {   

41        plistA = plistA->next;   

42       --lenA;    

43    }   

44    //一样长了   

45    //寻找公共节点   

46    while (plistA!=NULL && plistA != plistB)   

47    {   

48        plistA = plistA->next;   

49        plistB = plistB->next;   

50    }   

51    return plistA;   

52}