1 /*************************************************************************  2     > File Name: 35_FirstCommonNode.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年09月02日 星期五 20时52分28秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <malloc.h> 10  11 // 链表结构体 12 struct ListNode 13 { 14     int val; 15     struct ListNode* next; 16 }; 17  18 // 顺序输出链表 19 void PrintList(ListNode* head) 20 { 21     if (head == NULL) 22         return; 23     ListNode* temp = head; 24     printf("PrintList:\n"); 25     while (temp != NULL) 26     { 27         printf("%d ", temp->val); 28         temp = temp->next; 29     } 30     printf("\n"); 31 } 32  33 // 获取链表长度 34 int getListLength(ListNode* head) 35 { 36     int length = 0; 37     ListNode* p = head; 38     while (p) 39     { 40         length ++; 41         p = p->next; 42     } 43     return length; 44 } 45  46 // 寻找第一个公共结点 47 ListNode* FindFirstCommonNode(ListNode* head1, ListNode* head2) 48 { 49     int length1 = getListLength(head1); 50     int length2 = getListLength(head2); 51      52     ListNode* longList; 53     ListNode* shortList; 54     int diff; 55      56     if (length1 >= length2) 57     { 58         longList = head1; 59         shortList = head2; 60         diff = length1 - length2; 61     } 62     else 63     { 64         longList = head2; 65         shortList = head1; 66         diff = length2 - length1; 67     } 68      69     for (int i = 0; i < diff; ++i) 70         longList = longList->next; 71      72     while (longList && shortList && shortList!=longList) 73     { 74         longList = longList->next; 75         shortList = shortList->next; 76     } 77      78     if (longList == NULL) 79         printf("Not Find\n"); 80     else 81         printf("Find %d\n", longList->val); 82      83     return longList; 84 } 85  86 int main() 87 { 88     // 测试链表结构 89     ListNode* head1 = (ListNode*)malloc(sizeof(ListNode)); 90     head1->val = 1; 91     ListNode* p1 = head1; 92     for (int i = 0; i < 4; ++i) 93     { 94         ListNode* q1 = (ListNode*)malloc(sizeof(ListNode)); 95         q1->val = i + 2; 96         p1->next = q1; 97         p1 = q1; 98     } 99     p1->next = NULL;100     101     102     ListNode* head2 = (ListNode*)malloc(sizeof(ListNode));103     head2->val = 6;104     ListNode* p2 = head2;105     for (int i = 0; i < 4; ++i)106     {107         ListNode* q2 = (ListNode*)malloc(sizeof(ListNode));108         q2->val = i + 7;109         p2->next = q2;110         p2 = q2;111     }112     p2->next = NULL;113     114     p1->next = head2->next->next;115     116     PrintList(head1);117     PrintList(head2);118     119     FindFirstCommonNode(head1, head2);120 }