链表习题（5）-给定两个单链表，编写算法找出两个链表的公共结点

 1 /*给定两个单链表，编写算法找出两个链表的公共结点*/
 2 /*
 3     算法思想：两个链表有公共结点的话，那么从第一个公共结点开始，后面的结点都是相同的，不可
 4     能出现分叉。又由于两个链表的长度不一定一样，故不能同时遍历两个链表。
 5     可以先得到两个链表的长度l1,l2,设l1-l2=k,那么在教长的链表上遍历k个结点，在同步遍历两个链
 6     表，保证两个链表同时到达最后一个节点，这样也就保证了能够同时到达第一个公共结点。
 7 */
 8 LinkList SearchFirstCommon(LinkList L1, LinkList L2)
 9 {
10     int len1 = getLength(L1), len2 = getLength(L2);    //获取两个线性表的长度
11     LinkList longList, shortList;        //用于指向教长，较短链表的第一个结点
12     int dist;
13     if (len1 > len2)
14     {
15         longList = L1->next;
16         shortList = L2->next;
17         dist = len1 - len2;
18     }
19     else
20     {
21         longList = L2->next;
22         shortList = L1->next;
23         dist = len2 - len1;
24     }
25     while (dist--)
26     {
27         longList = longList->next;
28     }
29     while (longList!=NULL)
30     {
31         if (longList == shortList)    //找到公共结点，返回
32             return longList;
33         else
34         {
35             longList = longList->next;
36             shortList = shortList->next;
37         }
38     }
39     return NULL;    //没有公共结点
40 }