【编程题目】请修改 append 函数,利用这个函数实现两个非降序链表的并集

时间:2021-02-02 19:09:47

42.请修改 append 函数,利用这个函数实现(链表):
两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果,不能修改两个链表的数据。

感觉网上理解题意略有不同,我理解的题意:

只是输出最后的结果,不用生成一个新的链表,也不修改原有链表。

给的数据非降序就是 1 1 2 2 3 这样可以有重复数字的递增

输出时,不显示重复的数字。

基于这些理解,题目不难,代码如下:

/*
42.请修改 append 函数,利用这个函数实现(链表):
两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果,不能修改两个链表的数据。
start time = 19:29
end time = 19:57
*/ #include <iostream>
using namespace std; typedef struct List
{
int m_value;
List * p_next;
}List; void append(List * L1, List * L2)
{
List * p1 = L1;
List * p2 = L2;
//两个链表都没走空
while(p1 != NULL && p2 != NULL)
{
int v;
if(p1->m_value > p2->m_value)
{
v = p2->m_value;
cout << p2->m_value;
while(p2 != NULL && p2->m_value == v)
p2 = p2->p_next;
}
else if(p1->m_value < p2->m_value)
{
v = p1->m_value;
cout << p1->m_value;
while(p1 != NULL && p1->m_value == v)
p1 = p1->p_next;
}
else
{
v = p1->m_value;
cout << p1->m_value<<" ";
while(p1 != NULL && p1->m_value == v)
p1 = p1->p_next;
while(p2 != NULL && p2->m_value == v)
p2 = p2->p_next;
} if(p1 == NULL && p2 == NULL)
cout<<endl;
else
cout<<"->";
}
//若p1未走空
while(p1 != NULL)
{
int v = p1->m_value;
cout << p1->m_value;
while(p1 != NULL && p1->m_value == v)
p1 = p1->p_next;
if(p1 == NULL)
cout<<endl;
else
cout<<"->";
}
//若p2未走空
while(p2 != NULL)
{
int v = p2->m_value;
cout << p2->m_value;
while(p2 != NULL && p2->m_value == v)
p2 = p2->p_next;
if(p2 == NULL)
cout<<endl;
else
cout<<"->";
}
} void createList(List * &Head)
{
int data;
cin >> data;
if(data != )
{
Head = new List;
Head->m_value = data;
Head->p_next = NULL;
createList(Head->p_next);
}
}
int main()
{
List * L1 = NULL;
List * L2 = NULL;
createList(L1);
createList(L2);
append(L1, L2); return ;
}