8week

 关注
发布于: 2020 年 07 月 26 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
1.解法一：从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点。时间复杂度为O(n^2)。
﻿
2.遍历两个链表记录两个链表的长度，设较长的链表长度为len1,短的链表长度为len2，则先让较长的链表向后偏移(len1-len2)个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。时间复杂度为O(len1+len2)
typedef struct node_link
{
    int data;
    struct node_t *next; 
}Node;
﻿
node* NodeSearch(Node *head1, Node *head2)
{
    if(head1==NULL || head2==NULL)
    {
        return NULL;
    }
    Node *p1=head1;
    Node *p2=head2;
    
    int len1 = 0, len2 =0;
    int offset = 0;
    while(p1->next!=NULL)
    {
        p1 = p1->next;
        len1++;
    }
    while(p2->next!=NULL)
    {
        p2 = p2->next;
        len2++;
    }
    if(p1 != p2) //如果最后一个节点不相同,返回NULL
    {
        return NULL;
    }
    offset = abs(len1 - len2);
    if(len1 > len2)
    {
        p1 = head1;
        p2 = head2;
    }
    else
    {
        p1 = head2;
        p2 = head1;
    }
    for(int i=0; i<offset; i++)
    {
        p1 = p1->next;
    }
    while(p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}
﻿
发布于: 2020 年 07 月 26 日阅读数: 36
一叶知秋

 关注
还未添加个人签名 2018.05.13 加入
还未添加个人简介
评论 (1 条评论)

发布