两个链表的第一个公共节点详解编程语言

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

typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode;

【方案】
方案一：在第一条链表上遍历每个节点，每遍历到一个节点就到第二条链表上遍历整条链表，如果两条链表在一个节点上重合，这点即为公共节点，时间复杂度为O(mn)。

方案二：先把两条链表放在两个栈中，这样两条链表的尾节点就位于两个栈的顶部，然后比较两个栈顶的节点。如果相同，则把栈顶弹出再比较下一个栈顶，直到找到最后一个节点。时间复杂度和空间复杂度都是O(m+n),与方案一相比时间效率提高了，但是消耗了一定的空间。

方案三：因为单链表只有一个“next”指针指向下一个节点，如果两条链表有一个公共点，那么从第一个公共节点开始，之后的节点都相同，如下图所示。根据链表的这个特性，做出如下方案： 第一次遍历两条链表得到它们的长度，及算出长度差；第二次先在长链表上走长度差步，再同时遍历两条链表，第一个结合点即为所求。与方案二相比，时间复杂度都是O(m+n)，但是不需要辅助栈，提高了空间效率。

【解题思路】
1、求两条链表的长度及链表长度差。
2、在长链表上走“链表长度差”步。
3、同时遍历长短两条链表。
4、返回第一个公共节点

【代码】

unsigned int GetListLength(pList phead) 
{ 
    unsigned int length = 0; 
    pNode pnode = phead; 
    while (pnode != NULL) 
    { 
        ++length; 
        pnode = pnode->next; 
    } 
    return length; 
} 
 
pNode ListFirstCommomNode(pList phead1, pList phead2) 
{ 
    //求两条链表的长度及链表长度差 
    unsigned int length1 = 0; 
    length1 = GetListLength(phead1); 
    unsigned int length2 = 0; 
    length2 = GetListLength(phead2); 
    int lengthdif = length1 - length2; 
    pList plistlong = phead1; 
    pList plistshort = phead2; 
    if (length1 < length2) 
    { 
        plistlong = phead2; 
        plistshort = phead1; 
        lengthdif = length2 - length1;   
    } 
    //先在长链表上走“链表长度差”步 
    for (int i = 0; i < lengthdif; ++i) 
    { 
        plistlong = plistlong->next; 
    } 
    //同时遍历长短两条链表 
    while ((plistlong != NULL)  
        && (plistshort != NULL)  
        && (plistlong != plistshort)) 
    { 
        plistlong = plistlong->next; 
        plistshort = plistshort->next; 
    } 
    //得到第一个公共节点 
//Node pfirstcommomnode = plistlong; 
    return plistlong; 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
    assert(pplist); 
    *pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
    pNode cur = *pplist; 
    pNode pnode = NULL; 
    assert(pplist); 
    pnode = (pNode)malloc(sizeof(Node)); 
    if (pnode == NULL) 
    { 
        perror("PushBack::malloc"); 
        exit(EXIT_FAILURE); 
    } 
    pnode->data = x; 
    pnode->next = NULL; 
    if (cur == NULL) 
    { 
        *pplist = pnode; 
    } 
    else 
    { 
        while (cur->next != NULL) 
        { 
            cur = cur->next; 
        } 
        cur->next = pnode; 
    } 
} 
 
void Display(pList plist) 
{ 
    pNode cur = plist; 
    while (cur) 
    { 
        printf("%d-->", cur->data); 
        cur = cur->next; 
    } 
    printf("over/n"); 
} 
 
void PrintNode(pList plist) 
{ 
    pNode cur = plist; 
    printf("%d/n", cur->data); 
} 
 
void Destroy(pList *pplist) 
{ 
    pNode cur = *pplist; 
    assert(pplist); 
    while (cur) 
    { 
        pNode del = cur; 
        cur = cur->next; 
        free(del); 
    } 
    *pplist = NULL; 
} 
 
unsigned int GetListLength(pList phead) 
{ 
    unsigned int length = 0; 
    pNode pnode = phead; 
    while (pnode != NULL) 
    { 
        ++length; 
        pnode = pnode->next; 
    } 
    return length; 
} 
 
pNode ListFirstCommomNode(pList phead1, pList phead2) 
{ 
    //求两条链表的长度及链表长度差步 
    unsigned int length1 = 0; 
    length1 = GetListLength(phead1); 
    unsigned int length2 = 0; 
    length2 = GetListLength(phead2); 
    int lengthdif = length1 - length2; 
    pList plistlong = phead1; 
    pList plistshort = phead2; 
    if (length1 < length2) 
    { 
        plistlong = phead2; 
        plistshort = phead1; 
        lengthdif = length2 - length1;   
    } 
    //先在长链表上走“链表长度差”步 
    for (int i = 0; i < lengthdif; ++i) 
    { 
        plistlong = plistlong->next; 
    } 
    //同时遍历长短链表 
    while ((plistlong != NULL) && (plistshort != NULL) && (plistlong != plistshort)) 
    { 
        plistlong = plistlong->next; 
        plistshort = plistshort->next; 
    } 
    //得到第一个公共节点 
//Node pfirstcommomnode = plistlong; 
    return plistlong; 
} 
 
void test1() 
{ 
    pList plist; 
    pList plist1; 
    pList plist2; 
 
    pNode ret = NULL; 
 
    InitLinkList(&plist); 
    InitLinkList(&plist1); 
    InitLinkList(&plist2); 
 
    PushBack(&plist2, 6); 
    PushBack(&plist2, 7); 
 
    PushBack(&plist, 1); 
    PushBack(&plist, 2); 
    PushBack(&plist, 3); 
    pList tmp = plist; 
    while (tmp->next) 
    { 
        tmp = tmp->next; 
    } 
    tmp->next = plist2; 
    Display(plist); 
 
    PushBack(&plist1, 4); 
    PushBack(&plist1, 5); 
    pList cur = plist1; 
    while (cur->next) 
    { 
        cur = cur->next; 
    } 
    cur->next = plist2; 
    Display(plist1); 
 
    ret = ListFirstCommomNode(plist, plist1); 
    PrintNode(ret); 
    Destroy(&plist); 
} 
 
int main() 
{ 
    test1(); 
    system("pause"); 
    return 0; 
}

运行结果：

【测试】
1、功能测试
1）输入的两条链表没有公共节点；
2）第一个公共节点在链表的中间；
3）第一个公共节点在链表的头节点；
4）第一个公共节点在链表的尾节点；

2、特殊输入测试
输入的链表头节点是NULL指针