1. 问题描述：

A和B是两个单链表（带有表头节点），其中元素是递增有序的，设计一个算法，将A和B归并成一个按元素值非增减有序的链表C，C由链表A和B的节点组成

2. 思路分析：

① 我们知道头插法最终创建的链表的顺序与插入的顺序正好是相反的，所以我们可以修改之前的将两个递增有序的链表合并成一个非递减的链表程序，将头插法修改为尾插法

② 与头插法不同的是，头插法在while循环之后可以直接将指向链表C的指针指向剩余的没有插入完的链表的剩余部分，但是尾插法不可以这样，因为需要形成非递增的序列所以需要使用while循环将链表的剩余节点一个个地插入到链表C中

3. 下面是具体的C语言代码：

#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
	int data;
	LNode *next;
}LNode;
LNode *A, *B, *C;
void merge(LNode *A, LNode *B, LNode *&C){
	LNode *p = A->next;
	LNode *q = B->next;
	LNode *s;
	LNode *r;
	C = A;
	C->next = NULL;
	free(B);
	r = C;
	while(p != NULL && q != NULL){
		if(p->data <= q->data){
			s = p;
			//先要操作这一步否则后面的元素会找不到 
			p = p->next;
			s->next = r->next;
			r->next = s;
		}
		else{
			s = q;
			q = q->next;
			s->next = r->next;
			r->next = s;
		}
	}
	while(p != NULL){
		s = p;
		p = p->next;
		s->next = r->next;
		r->next = s;
	}
	while(q != NULL){
		s = q;
		q = q->next;
		s->next = r->next;
		r->next = s;
	}
}

void createLinkList(){
	LNode *pa;
	LNode *pb;
	A = (LNode*)malloc(sizeof(LNode));
	B = (LNode*)malloc(sizeof(LNode));
	pa = A;
	pb = B;
	pa->next = NULL;
	pb->next = NULL;
	
	for(int i = 1; i <= 10; i += 2){
		LNode *newNode = (LNode*)malloc(sizeof(LNode));
		newNode->data = i;
		pa->next = newNode;
		pa = pa->next;
	} 
	pa->next = NULL;
	for(int i = 2; i <= 8; i += 2){
		LNode *newNode = (LNode*)malloc(sizeof(LNode));
		newNode->data = i;
		pb->next = newNode;
		pb = pb->next;
	} 
	pb->next = NULL;
}

int main(void){
	createLinkList();
	merge(A, B, C);
	LNode *p = C;
	while(p->next != NULL){
		printf("%d ", p->next->data);
		p = p->next;
	} 
	return 0;
}