当前位置：首页 > news >正文

链表合并不解之处

news 2026/5/11 20:00:03

我在做一元多次的方程合并时，在节点函数中定义系数和指数，相当于给你两个La，Lb链表，按照节点中的指数大小排序，对他们系数进行合并。我有两种方式进行编写。

题目：

第一行包含一个整数 nn，表示第一个多项式 LaLa 的项数；

接下来 nn 行，每行表示多项式的一项，包含两个整数，分别表示系数和指数；

接下来一行包含一个整数 mm，表示第二个多项式 LbLb 的项数；

接下来 mm 行，每行表示多项式的一项，包含两个整数，分别表示系数和指数。

数据保证两个多项式都是按指数从小到大的顺序输入。

1≤n,m≤10001≤n,m≤1000
−1000≤系数≤1000−1000≤系数≤1000
1≤指数≤20001≤指数≤2000

输出格式

按指数从小到大的顺序，输出 LaLa 与 LbLb 相加后得到的多项式，每项占一行，每行输出两个整数，分别表示系数和指数，中间用空格隔开。

你只需要输出系数不为 00 的项。

第一种：

#include <iostream> #include <cstdlib> using namespace std; typedef struct N { int x, y; struct N *next; } Node, *list; list Creatlist(int n) { list L = (list)malloc(sizeof(Node)); L->next = NULL; list tail = L; for (int i = 0; i < n; i++) { list p = (list)malloc(sizeof(Node)); cin >> p->x >> p->y; p->next = NULL; tail->next = p; tail = p; } return L; } list mixab(list La, list Lb) { list pa = La->next; list pb = Lb->next; list Lc = (list)malloc(sizeof(Node)); Lc->next = NULL; list pc = Lc; while (pa && pb) { if (pa->y == pb->y) { int sum = pa->x + pb->x; if (sum != 0) { list newNode = (list)malloc(sizeof(Node)); newNode->x = sum; newNode->y = pa->y; newNode->next = NULL; pc->next = newNode; pc = newNode; } pa = pa->next; pb = pb->next; } else if (pa->y < pb->y) { list newNode = (list)malloc(sizeof(Node)); newNode->x = pa->x; newNode->y = pa->y; newNode->next = NULL; pc->next = newNode; pc = newNode; pa = pa->next; } else { list newNode = (list)malloc(sizeof(Node)); newNode->x = pb->x; newNode->y = pb->y; newNode->next = NULL; pc->next = newNode; pc = newNode; pb = pb->next; } } while (pa) { list newNode = (list)malloc(sizeof(Node)); newNode->x = pa->x; newNode->y = pa->y; newNode->next = NULL; pc->next = newNode; pc = newNode; pa = pa->next; } while (pb) { list newNode = (list)malloc(sizeof(Node)); newNode->x = pb->x; newNode->y = pb->y; newNode->next = NULL; pc->next = newNode; pc = newNode; pb = pb->next; } return Lc; } void printlist(list Lc) { list p = Lc->next; while (p) { cout << p->x << " " << p->y << endl; p = p->next; } } int main() { int n, m; cin >> n; list La = Creatlist(n); cin >> m; list Lb = Creatlist(m); list Lc = mixab(La, Lb); printlist(Lc); return 0; }

我在合并La,Lb得到Lc过程中，在每次将La和Lb中的系数值和指数值附给Lc时通过建立新的有空间的节点，相当于从头建立Lc这个链表，用新的节点直接代替a，b的节点，

第二种：

#include<iostream> #include<cstdlib> using namespace std; typedef struct N { int x, y; struct N*next; } Node,*list; int n, m; list Creatlist(int n) { list L = (list)malloc(sizeof(Node)); L->next = NULL; list tail = L; for (int i = 1; i <= n; i++) { list p = (list)malloc(sizeof(Node)); cin >> p->x >> p->y; tail->next = p; p->next = NULL; tail = p; } return L; } list mixab(list &La, list &Lb) { list pa = La->next; list pb = Lb->next; list pc; list Lc=(list)malloc(sizeof(Node));; Lc->next = NULL; pc = Lc; while (pa && pb) { if (pa->y == pb->y) { if (pa->x + pb->x != 0) { list temp = pb; pa->x += pb->x; pb = pb->next; free(temp); pc->next = pa; pc = pa; pa = pa->next; } else { list t1 = pa; list t2 = pb; pa = pa->next; pb = pb->next; free(t1); free(t2); } } else if (pa->y < pb->y) { pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } } while (pa) { pc->next = pa; pc = pa; pa = pa->next; } while (pb) { pc->next = pb; pc = pb; pb = pb->next; } free(La); free(Lb); return Lc; } void printlist(list &Lc){ list pc=Lc->next; while(pc){ cout<<pc->x<<" "<<pc->y<<endl; pc=pc->next; } } int main(){ cin>>n; list La=Creatlist(n); cin>>m; list Lb=Creatlist(m); list Lc=mixab(La,Lb); printlist(Lc); return 0; }

这个是有错误的，这个方法我想通过直接将Lc的头节点直接指向pa快速得到一个链表，再通过La和Lb的比较进行对Lc进行修改，但是这个超时了。我询问过AI，AI说我的代码存在链表节点指向空指针的情况，出现了死循环，但是我不太明白它的意思。我想知道我的代码具体错在什么地方；怎么进行解决；为什么会出现这种情况，还有其问题原理所在；我在之后的运用中怎么避免这种情况。谢过各位大佬的解答。

查看全文

http://www.jsqmd.com/news/542171/