单链表的基本操作

第1关：单链表的插入操作

任务描述

本关任务：编写单链表的初始化、插入、遍历三个操作函数。

测试说明

平台会对你编写的代码进行测试：

测试输入：
5
12 47 5 8 69
1
99
预期输出：
插入成功，插入后单链表如下：
99 12 47 5 8 69

测试输入：
5
12 47 5 8 69
7
99
预期输出：
插入位置不合法，插入失败！

输入说明
第一行输入单链表的数据元素的个数M；
第二行输入单链表M个整数；
第三行输入要插入元素的位置；
第四行输入要插入的数据元素的值。

输出说明
第一行输出插入是否成功的提示信息；
如果插入成功，第二行输出插入元素后的单链表所有元素；如果插入失败，则不输出第二行。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 单链表类型定义 */
typedef struct LNode
{	
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

void InitList(LinkList &L);
int ListInsert(LinkList L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));

int main()               //main() function 
{	
     LinkList A;
     ElemType e;
     InitList(A);
      int n,i;
     // cout<<"Please input the list number ";
     cin>>n;
     for(i=1;i<=n;i++)
        { 
		   cin>>e;
         ListInsert(A, i, e);
       }
	//cout<<"请输入插入的位置："<<endl;
	cin>>i;
	//cout<<"请输入插入的值："<<endl;
	input(e);
	if(  ListInsert(A,i,e) )
    {
      cout<<"插入成功，插入后单链表如下："<<endl;
      ListTraverse(A,output) ;
    }
    else
    	cout<<"插入位置不合法，插入失败！"<<endl;
    return  0;  
 }


/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
 {
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 
	// 操作结果：构造一个空的单链表L
	/********** Begin **********/ 
	L=(LinkList)malloc(sizeof(LNode));
	if(!L) exit(-1);
	L->next=NULL;
	/********** End **********/
}
int ListInsert(LinkList L,int i,int e) 
{
	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	/********** Begin **********/ 
	int j=0;
	LinkList p=L,s;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(!p || j>i-1) return 0;
	s=(LinkList)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return 1;
	/********** End **********/
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	/********** Begin **********/ 
	LinkList p=L->next;
	while(p){
		vi(p->data);
		p=p->next;
	}
	printf("\n");
	/********** End **********/
}
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

第2关：单链表的删除操作

任务描述

本关任务：编写单链表的删除操作函数。

测试说明

平台会对你编写的代码进行测试：

测试输入：
5
12 47 5 8 69
1
预期输出：
删除成功，删除后单链表如下：
47 5 8 69
删除元素的值：12

测试输入：
5
12 47 5 8 69
6
预期输出：
删除位置不合法，删除失败！

输入说明
第一行输入单链表的长度M；
第二行输入单链表的M个整数；
第三行输入要删除元素的位置；

输出说明
第一行输出删除是否成功的提示信息；
如果删除成功，第二行输出删除元素后的单链表；第三行输出删除的数据元素；如果删除位置不合法，不输出第二行和第三行。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
int ListDelete(LinkList L,int i,ElemType &e);
void ListTraverse(LinkList L,void(*vi)(ElemType));

int main()               //main() function 
{	
	LinkList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入删除的位置："<<endl;
	cin>>i;	
	if(  ListDelete(A,i,e) )
	{
		cout<<"删除成功，删除后单链表如下："<<endl;
		ListTraverse(A,output) ;
		cout<<"删除元素的值：";
	   output(e);
   	   cout<<endl;
	}
	else
		cout<<"删除位置不合法，删除失败！"<<endl;
}



/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 构造一个空的单链表L	
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空
	
}

int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	LinkList p,s;
	p = L;   
	int j = 0;
	while (p && j < i-1) {  // 寻找第i-1个结点
		p = p->next;
		++j;
	} 
	if (!p || j > i-1) 
		return 0;                   // i小于1或者大于表长
	s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点
	s->data = e;  s->next = p->next;      // 插入L中
	p->next = s;
	return 1;
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 调用函数vi()依次输出单链表L的每个数据元素
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");	
}

int  ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改变L
{ 
	// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
	/********** Begin **********/ 
	int j=0;LinkList p=L,r;
	while(p->next && j<i-1){
		p=p->next;
		j++;
	}
	if(!p->next || j>i-1) return 0;
	r=p->next;
	p->next=r->next;
	e=r->data;
	free(r);
	return 1;
	/********** End **********/
}
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

第3关：单链表的按照序号查找值操作

任务描述

本关任务：编写单链表按照序号i查找数据元素值操作函数。

测试说明

平台会对你编写的代码进行测试：

测试输入：
10
12 47 5 8 6 92 45 63 75 38
8

预期输出：
查找成功！
第8个元素的值：
63

测试输入：
10
12 47 5 8 6 92 45 63 75 38
11

预期输出：
查找失败！

输入说明
第一行输入单链表的长度M；
第二行输入单链表的M个整数；
第三行输入要查找的序号。

输出说明
第一行输出按照序号查找是否成功的提示信息；
如果查找成功，输出查找的数据元素的值；如果查找失败，则不输出。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int GetElem(LinkList L,int i,ElemType &e) ;

int main()               //main() function 
{	
	LinkList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入查找的序号："<<endl;
	cin>>i;	
	if(  GetElem(A,i,e) )
	{
		cout<<"查找成功！"<<endl;
		cout<<"第"<<i<<"个元素的值："<<endl;
	    output(e);
        cout<<endl;
	}
	else
		cout<<"查找失败！"<<endl;
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表L
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空
	
}

int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	LinkList p,s;
	p = L;   
	int j = 0;
	while (p && j < i-1) {  // 寻找第i-1个结点
		p = p->next;
		++j;
	} 
	if (!p || j > i-1) 
		return 0;                   // i小于1或者大于表长
	s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点
	s->data = e;  s->next = p->next;      // 插入L中
	p->next = s;
	return 1;
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}

int GetElem(LinkList L,int i,ElemType &e) 
{ 
	// L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回1，否则返回0
	/********** Begin **********/ 
	int j=1;
	LinkList p=L->next;
	while(p && j<i){
		p=p->next;
		j++;
	}
	if(!p || j>i) return 0;
	e=p->data;
	return 1;  
	/********** End **********/
}
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

第4关：单链表的按照值查找结点位序的操作

任务描述

本关任务：编写单链表的按照值查找结点位序的操作函数。

测试说明

平台会对你编写的代码进行测试：

测试输入：
10
12 47 5 8 6 92 45 63 75 38
92

预期输出：
查找成功！
92 是单链表第6个元素

测试输入：
10
12 47 5 8 6 92 45 63 75 38
93

预期输出：
查找失败！

输入说明
第一行输入单链表的长度M；
第二行输入单链表的M个整数；
第三行输入要查找的数据元素的值。

输出说明
第一行输出按照值查找是否成功的提示信息；
如果查找成功，第二行输出查找元素的逻辑序号；如果查找失败，则不输出。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;


/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType));
int main()               //main() function 
{	
	LinkList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入查找的元素："<<endl;
	cin>>e;	
	i=LocateElem(A,e,equals);
	if( i ) 
	{
		cout<<"查找成功！"<<endl;		
	    output(e);
      cout<<"是单链表第"<<i<<"个元素"<<endl;
	}
	else
		cout<<"查找失败！"<<endl;
}



/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表L
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空	
}

int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	LinkList p,s;
	p = L;   
	int j = 0;
	while (p && j < i-1) {  // 寻找第i-1个结点
		p = p->next;
		++j;
	} 
	if (!p || j > i-1) 
		return 0;                   // i小于1或者大于表长
	s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点
	s->data = e; 
    s->next = p->next;      // 插入L中
	p->next = s;
	return 1;	
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}

int LocateElem(LinkList L,ElemType e,int (*equal)(ElemType,ElemType))
{ 
	// 初始条件: 单链表L已存在，equal()是数据元素判定函数(满足为1，否则为0)
	// 操作结果: 返回L中第1个与e满足关系equal()的数据元素的位序，若这样的数据元素不存在，则返回值为0
	/********** Begin **********/ 
	int i=0;
	LinkList p=L->next;
	while(p){
		i++;
		if(equal(p->data,e)) return i;
		p=p->next;
	}
	return 0;
	/********** End **********/
}
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

第5关：单链表的逆置操作

任务描述

本关任务：编写单链表的逆置操作函数。

测试说明

平台会对你编写的代码进行测试：

测试输入：
10
12 47 5 8 6 92 45 63 75 38

预期输出：
逆置单链表：
38 75 63 45 92 6 8 5 47 12

输入说明
第一行输入单链表的长度M；
第二行输入单链表的M个整数；

输出说明
第一行输出提示信息；
第二行输出逆置后的单链表。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void reverse (LinkList &L);
int main()               //main() function 
{	
	LinkList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	cout<<"逆置单链表："<<endl;
	reverse(A);
	ListTraverse(A,output) ;	
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表L
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空	
}

int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	LinkList p,s;
	p = L;   
	int j = 0;
	while (p && j < i-1) {  // 寻找第i-1个结点
		p = p->next;
		++j;
	} 
	if (!p || j > i-1) 
		return 0;                   // i小于1或者大于表长
	s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点
	s->data = e;  s->next = p->next;      // 插入L中
	p->next = s;
	return 1;	
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");	
}

void reverse (LinkList &L)
{  
	//逆置L指针所指向的单链表
	/********** Begin **********/ 
	LinkList p,q;
	p=L->next;
	L->next=NULL;
	while(p != NULL){
		q=p;
		p=p->next;
		q->next=L->next;
		L->next=q;
	}
	/********** End **********/
}
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

第6关：两个有序单链表的合并操作

任务描述

本关任务：分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表。要求合并后的单链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。

测试说明

平台会对你编写的代码进行测试：

测试输入：
5
10 15 20 25 30
6
12 22 32 42 52 62

输入说明
第一行输入有序表A的长度M；
第二行依次输入有序表A的M个有序的整数；
第三行输入有序表B的长度N；
第四行依次输入有序表B的N个有序的整数。

预期输出：
合并两个有序单链表：
10 12 15 20 22 25 30 32 42 52 62

输出说明
第一行输出提示信息；
第二行输出合并后的有序单链表所包含的M+N个有序的整数。

代码如下

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);

int main()               //main() function 
{	
	LinkList A,B,C;
	ElemType e;
	InitList(A);
	InitList(B);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(B, i, e);
	}
	cout<<"合并两个有序单链表："<<endl;
	MergeList(A,B,C);	
	ListTraverse(C,output) ;	
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 	// 操作结果：构造一个空的单链表L
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空	
}

int ListInsert(LinkList &L,int i,ElemType e) 
{	// 在带头结点的单链线性表L的第i个元素之前插入元素e  
	LinkList p,s;
	p = L;   
	int j = 0;
	while (p && j < i-1) {  // 寻找第i-1个结点
		p = p->next;
		++j;
	} 
	if (!p || j > i-1) 
		return 0;                   // i小于1或者大于表长
	s = (LinkList)malloc(sizeof(LNnode));  // 生成新结点
	s->data = e;  s->next = p->next;      // 插入L中
	p->next = s;
	return 1;	
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");	
}

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) 
{
	// 已知单链线性表La和Lb的元素按值非递减排列。
	// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
	/********** Begin **********/ 
	LinkList pa,pb,pc;
	pa=La->next;
	pb=Lb->next;
	Lc=La;
	pc=Lc;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next=pa;pc=pa;pa=pa->next;
		}else{
			pc->next=pb;pc=pb;pb=pb->next;
		}
	}
    pc->next=pa?pa:pb;
	free(Lb);
	/********** End **********/
}
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