写点什么

练习 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



用户头像

还未添加个人签名 2018.11.15 加入

还未添加个人简介

评论

发布
暂无评论
练习8-1