已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。
输入样例:
1 2 5 -1
2 4 5 8 10 -1
输出样例:
2 5
#include
using namespace std;
typedef struct Lnode
{
int data;
Lnode *next;
}Lnode, *Linklist;
void creat_a( Linklist &La )
{
Linklist p, q;
La = new Lnode;
La->next = NULL;
q = La;
while (1)
{
p = new Lnode;
cin>>p->data;
if ( p->data == -1 )
{
return;
}
p->next = NULL;
q->next = p;
q = p;
}
}
void creat_b ( Linklist &Lb )
{
Linklist p, q;
Lb = new Lnode;
Lb->next = NULL;
q = Lb;
while(1)
{
p = new Lnode;
cin>>p->data;
if ( p->data == -1 )
{
return;
}
p->next = NULL;
q->next = p;
q = p;
}
}
void jiaoji ( Linklist &La, Linklist &Lb, Linklist &Lc )
{
Linklist pa, pb, q, r;
Lc = new Lnode;
Lc->next = NULL;
pa = La;
pb = Lb;
r = Lc;
while ( pa->next != NULL )
{
while ( pb->next != NULL )
{
if ( pa->next->data == pb->next->data )
{
q = new Lnode;
q->data = pb->next->data;
q->next = NULL;
r->next = q;
r = q;
}
pb = pb->next;
}
pa = pa->next;
}
}
void Print(Linklist Lc)
{
Linklist p = Lc->next;
if ( p == NULL )
{
cout << "NULL";
}
while (p != NULL)
{
cout << p->data;
if (p->next != NULL)
{
cout << " ";
}
p = p->next;
}
}
int main ()
{
Linklist La, Lb, Lc;
creat_a (La);
creat_b(Lb);
jiaoji (La, Lb, Lc);
Print (Lc);
return 0;
}
这个是找交集的程序吗,我有更简单的
下面是用C++实现求两个非降序链表的交集的代码:
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 创建链表
ListNode* createList() {
ListNode *head = NULL, *tail = NULL;
int num;
while (cin >> num && num != -1) {
ListNode *node = new ListNode(num);
if (head == NULL) {
head = tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}
// 求两个非降序链表的交集
ListNode* getIntersection(ListNode *l1, ListNode *l2) {
ListNode *head = NULL, *tail = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
l1 = l1->next;
} else if (l1->val > l2->val) {
l2 = l2->next;
} else {
ListNode *node = new ListNode(l1->val);
if (head == NULL) {
head = tail = node;
} else {
tail->next = node;
tail = node;
}
l1 = l1->next;
l2 = l2->next;
}
}
return head;
}
// 输出链表
void printList(ListNode *head) {
if (head == NULL) {
cout << "NULL" << endl;
return;
}
ListNode *p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
int main() {
ListNode *l1 = createList();
ListNode *l2 = createList();
ListNode *l3 = getIntersection(l1, l2);
printList(l3);
return 0;
}
该程序通过函数createList分别创建两个链表,然后通过函数getIntersection求出两个链表的交集,最后通过函数printList输出结果。其中,在函数getIntersection中使用了双指针法来求解交集。时间复杂度为$O(m+n)$,其中$m$和$n$分别是两个链表的长度。
参考GPT和自己的思路,根据您提供的代码,我发现在 creat_a() 和 creat_b() 中,程序读入的是非降序序列,但是没有考虑输入的数是否按照非降序排列,因此输入的数可能存在乱序的情况,这就导致了在找链表交集的过程中无法正确判断是否存在相同的元素。
为了解决这个问题,您可以在读入链表时,判断当前读入的数是否比上一个读入的数小,如果小的话则说明输入的非降序序列被破坏了,可以考虑退出程序或者重新读入。
另外,您的代码中也存在一些细节问题,例如在 Print() 函数中,当链表为空时应该输出 NULL 而不是空字符串,您可以修改为以下代码:
void Print(Linklist Lc)
{
if (Lc->next == NULL) {
cout << "NULL";
return;
}
Linklist p = Lc->next;
while (p != NULL) {
cout << p->data;
if (p->next != NULL) {
cout << " ";
}
p = p->next;
}
}