Question

如何将两个递增单链表合并为一个递减单链表，并保留原有节点。求大神给出算法并注释，菜鸟诚心想学习。

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

Answer 1

/*采用方法：随机创建两个整型数组，再把它们分别按升序排列，然后用数组元素创建两个链表（升序）list1和list2。然后按要求进行合并。最后输出合并结果，销毁链表*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
}NODE,*PNODE, *LinkList;

/*比较函数，用于qsort排序时回调*/
int CompareInt(const void *s1, const void *s2)
{
int x= *(int *)s1;
int y= *(int *)s2;
return(x-y);
}
/*根据数组x中的n个元素排序后创建*/
LinkList CreateLst(int x[], int n)
{
if(x==NULL || n<=0) return NULL;
qsort((void *)x, n, sizeof(int), CompareInt);/*按升序排列数组x的元素*/
int i=n;
PNODE p, head=NULL;
while(i--)
{
p = (NODE *)calloc(1, sizeof(NODE));
p->data = x[i];
if(head==NULL)
{
head = p;
p->next = NULL;
}
else
{
p->next = head;
head = p; //头插法创建链表
}
}
return head;
}
/*销毁链表*/
void DestroyList(LinkList list)
{
if(list == NULL) return;
NODE * p=list;
while(list != NULL)
{
list = list->next;
free(p);
p = list;
}
}
/*打印链表*/
void printList(LinkList list)
{
while(list!=NULL)
{
printf("%d ", list->data);
list = list->next;
}
printf("\n");
return;
}
/*交换两个链表的指针指向，使得list指向的链表表头结点*/
void swapList(LinkList * plist1, LinkList * plist2)
{
if((plist1 == NULL) || (plist2 == NULL)) return ;
LinkList r1 = *plist1;
LinkList r2 = *plist2;
LinkList temp;
if(r1->data >=r2->data)
{
temp = *plist1;
*plist1 = *plist2;
*plist2 = temp;
}

}
/*合并递增链表为递减单链表并保留结点（不用创建新结点）*/
LinkList joinLists(LinkList list1, LinkList list2)
{
LinkList list3, p;

swapList(&list1, &list2);/*交换后list1指向的链表结点值不大于list2指向的链表结点值*/

list3 = list1;
list1 = list1->next;
list3->next = NULL;

while(list1!=NULL && list2 !=NULL)
{
while(list1!=NULL && (list1->data <= list2->data))
{
p = list1;
list1 = list1->next;
p->next = list3;
list3 = p;//采用头插法
}
if(list1 == NULL ) break;
swapList(&list1, &list2);/*交换后list1指向的链表结点值不大于list2指向的链表结点值*/
}
/*把某一个没用完的结点用头插法插入结果链表*/
if(list2 == NULL)
{
while(list1 != NULL)
{
p = list1;
list1 = list1->next;
p->next = list3;
list3 = p;//采用头插法
}
}else if(list1 == NULL)
{
while(list2 != NULL)
{
p = list2;
list2 = list2->next;
p->next = list3;
list3 = p;//采用头插法
}
}

return list3;
}
#define M 2
#define N 4
int main()
{

int x[M], y[N];
int i=0;
LinkList list1, list2, joined;
srand(time(NULL));
while(i<M)
{
x[i++] = rand()%100;
}

i=0;
while(i<N)
{
y[i++] = rand()%100;
}
list1 = CreateLst( x, M );
list2 = CreateLst( y, N );
printf("链表1数据:\n");
printList(list1);
printf("链表2数据:\n");
printList(list2);

joined = joinLists(list1, list2);
printf("合并链表数据:\n");
printList(joined);

DestroyList(joined);
return 0;
}

Answer 2

首先需要算出两个单链表的元素个数，定义一个指针数组 ，元素个数等于链表元素的个数，然后数组的每个元素指向 原链表中结点的前一个元素，后面排序时需要使用。
然后 比较两个单链表的最大值，作为 递减链表的第一个元素，然后逐个判断 链表1和链表2 的较大值，也就是说从后往前比较，这时就会用到 前面定义的数组元素。

Answer 3

node *mergelink(node *p, node *q)
{
node *h, *r;
h = (node*) malloc (sizeof(node));
h->next = NULL;
r = h;
while (p != NULL && q != NULL)
{
if (p->data <= q->data)
{
r->next = p;
r = p;
p = p->next;
}
else
{
r->next = q;
r = q;
q = q->next;
}
}

if (p == NULL)
r->next = q;
if (q == NULL)
r->next = p;

p = h->next;
h = h->next;
free(p);
return h;
}