练习 8-1

关注
发布于: 2020 年 07 月 29 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
    请用（伪）代码描述算法，并给出时间复杂度。
﻿
答：
    先获得两个链表的长度，然后在较长的链表上先走若干步(两链表长度之差)，接着同时在两个链表上遍历，找到的第一个相同的节点就是他们的第一个公共节点。时间复杂度O(m + n)（第一个链表长度为m，第二个链表的长度为n）
﻿
#include <cstdlib>
#include <complex>
#include <iostream>
using namespace std;
struct DataNode
{
    DataNode *next = NULL;
    int val = 0;
};
struct list
{
    DataNode* head = NULL;
    size_t length = 0;
    void add(int val)
    {
        length++;
        auto dn = new DataNode();
        dn->val = val;
        dn->next = NULL;
        if (head == NULL)
        {
            head = dn;
            return;
        }
        DataNode* p = head;
        while (p->next)
        {
            p = p->next;
        }
        p->next = dn;
    }
    void del(int val)
    {
        if (!head)
        {
            return;
        }
        if (head->val == val)
        {
            DataNode* d = head;
            head = head->next;
            delete d;
            length--;
            return;
        }
        DataNode* prev = head;
        while (prev->next);
        {
            if (prev->next->val == val)
            {
                DataNode* d = prev->next;
                prev->next = d->next;
                delete d;
                length--;
                return;
            }
            prev->next = prev->next->next;
        }
    }
};
DataNode* findFirstCommonNode(list* l1, list* l2)
{
    int gap = l1->length - l2->length;
    if (gap < 0)
    {
        gap = 0 - gap;
    }
    list* longList = l1;
    list* shortList = l2;
    if (l1->length < l2->length)
    {
        longList = l2;
        shortList = l1;
    }
    DataNode* shortNode = shortList->head;
    DataNode* longNode = longList->head;
    for (int i = 0; i < gap; ++i)
    {
        longNode = longNode->next;
    }
    while (shortNode && longNode)
    {
        if (shortNode == longNode)
        {
            return shortNode;
        }
        shortNode = shortNode->next;
        longNode = longNode->next;
    }
    return NULL;
}
/*
 * 
 */
int main(int argc, char** argv)
{
    list* l1 = new list();
    list* l2 = new list();
    list* l3 = new list();
    for (int i = 1; i < 11; ++i)
    {
        l1->add(i * 10);
    }
    for (int i = 1; i < 110; ++i)
    {
        l2->add(i * 100);
    }
    for (int i = 1; i < 1100; ++i)
    {
        l3->add(i * 1000);
    }
    DataNode* prev = l1->head;
    while (prev->next)
    {
        prev = prev->next;
    }
    prev->next = l3->head;
    prev = l2->head;
    while (prev->next)
    {
        prev = prev->next;
    }
    prev->next = l3->head;
    std::cout << "l3 fistNode: " << l3->head->val << std::endl;
    DataNode* n = findFirstCommonNode(l1, l2);
    if (n)
    {
        std::cout << "fistNode n: " << n->val << std::endl;
    }
    return 0;
}
输出结果: 
l3 fistNode: 1000
fistNode n: 1000
﻿
发布于: 2020 年 07 月 29 日阅读数: 46
闷骚程序员

关注
还未添加个人签名 2018.11.15 加入
还未添加个人简介
发布
暂无评论
创作场景

练习 8-1

闷骚程序员

评论
