编写算法将两个递增单链表合并成一个递减的线性表 20
节点结构：
typedef struct node{
int data;
struct node *next;
} linknode,*link;
link Union(link la,lb)
以上就是题目了，这个节点结构怎么用没看懂TAT，能不能帮我写下这道题的代码，大体思路我觉得就是先按递增合并再反转，但是每一步过度的细节处理的不好，麻烦在每一步过度的时候注释详细一点好么谢谢QAQ 展开
/*将两个递增单链表合并成一个递减单链表*/
/*
算法思想：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将较小的
结点链入链表中，同时后移工作指针。由于结果链表是递减的，故使用头插法建立新链表。比较结束后，
可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。
*/
void Union_List(LinkList& La,LinkList& Lb)
{
LNode *r, *pa = La->next, *pb = Lb->next; //pa,pb分别是La,Lb的工作指针
La->next = NULL; //将La作为结果链表的头指针
while (pa&&pb)
{
if (pa->data <= pb->data)
{
r = pa->next; //r暂存pa的后继结点指针
pa->next = La->next; //头插法插入pa所指结点
La->next = pa;
pa = r;
}
else
{
r = pb->next;
pb->next = La->next;
La->next = pb;
pb = r;
}
}
while (pa) //处理剩下的结点
{
r = pa->next;
pa->next = La->next;
La->next = pa;
pa = r;
}
while (pb)
{
r = pb->next;
pb->next = La->next;
La->next = pb;
pb = r;
}
free(Lb);
}
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
typedef struct node
{
int data;
struct node *next;
}node,list;
list *merge(list *a,list *b) /*合并链表*/
{
list *rt=NULL,*now=NULL,*nc=NULL;
while (a&&b)
{
if (a->data>=b->data) {
nc=a;
a=a->next;
}
else {
nc=b;
b=b->next;
}
if (rt) {
now->next=nc;
now=now->next;
}
else rt=now=nc;
}
if (a) now->next=a;
else now->next=b;
return rt;
}
list *reverse(list **lp) /*反转列表*/
{
list *f=*lp,*m=NULL,*l=NULL;
while (f)
{
m=f->next ;
f->next=l;
l=f;
f=m;
}
return *lp=l;
}
list *insert(list *a,int c)
{
node *b=NULL;
if (a) {
a->next=insert(a->next,c);
b=a;
}
else {
b=malloc(sizeof(node));
b->data=c;
b->next=NULL;
}
return b;
}
void prt(list *p)
{
while (p) {
printf("%d ",p->data);
p=p->next;
}
}
int main(void)
{
list *a=NULL, *b=NULL;
int i;
for (i = 10; i>0; i-=2) {
a=insert(a,i);
b=insert(b,i-1);
}
printf("A:\t");
prt(a);
printf("\nB:\t");
prt(b);
a=reverse((a=merge(a,b),&a));
printf("\nA+B:\t");
prt(a);
return 0;
}
这个节点结构和题目给的不一样啊TAT
