将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。_将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来

数据结构与算法-第二章线性表课后习题-课本第53页2.2
题目:将两个非递减的有序链表合并为一个非递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。

/*数据结构与算法-第二章线性表课后习题
*题目:将两个非递减的有序链表合并为一个非递增的有序链表。
*     要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。
*     表中允许有重复的数据。
*编译环境:VC 6.0
*/
typedef struct listnode
{
	int data;
	struct listnode *next;
}listnode,*link;
typedef struct
{
	link head;
	int len;
}Sqlist;
void initList(Sqlist &list)
{
	list.head=(link)malloc(sizeof(listnode));
	list.len=0;
	list.head->next=NULL;
}
int ListInsert(Sqlist &list,int i,int num)
{
	link p,q;
	int j=0;
	q=list.head;
	while(q && j<i-1)
	{
		q=q->next;
		j++;
	}
	if(!q || j>i-1)return ERROR;
	p=(link)malloc(sizeof(listnode));
	p->data=num;
	p->next=q->next;
	q->next=p;
	list.len++;
	return OK;
}
void printList(Sqlist &list)
{
	link p=list.head->next;
	while(p)
	{
		printf("%d,",p->data);
		p=p->next;
	}
	printf("\n");
}
void mergeList(Sqlist &la,Sqlist &lb,Sqlist &lc)
{
	link lista,listb,listc;
	lista=la.head->next;
	listb=lb.head->next;
	lc.head=la.head;
	la.head->next=NULL;
	while(lista && listb)
	{
		if(lista->data<=listb->data)
		{
			listc=lista->next;
			lista->next=lc.head->next;
			lc.head->next=lista;
		    lista=listc;
		}
		else
		{
			listc=listb->next;
			listb->next=lc.head->next;
			lc.head->next=listb;
		    listb=listc;
		}
	}
	while(lista)
	{
		listc=lista->next;
		lista->next=lc.head->next;
		lc.head->next=lista;
		lista=listc;
	}
	while(listb)
	{
		listc=listb->next;
		listb->next=lc.head->next;
		lc.head->next=listb;
		listb=listc;
	}
	delete lb.head;
}
int main()
{
	Sqlist list1,list2,list3;
	int num,count=0,flag;
	initList(list1);
	printf("输入la,并以-1结束:");
	scanf("%d",&num);
	count++;
	while(num!=-1)
	{
		flag=ListInsert(list1,count,num);
		scanf("%d",&num);
		count++;
	}
	count=0;
	initList(list2);
	printf("输入lb,并以-1结束:");
	scanf("%d",&num);
	count++;
	while(num!=-1)
	{
		flag=ListInsert(list2,count,num);
		scanf("%d",&num);
		count++;
	}
	printf("la:");
	printList(list1);
	printf("lb:");
	printList(list2);
	mergeList(list1,list2,list3);
	printf("lc:");
	printList(list3);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

编译结果：

并没有参考只是保存网址的链接：
https://wenku.baidu.com/view/3608bdaa294ac850ad02de80d4d8d15abe23008a.html