c语言将递增有序单链表和递减有序单链表在原空间内合成一个递增有序单链表（8）

这里我的思路就是：先将递减的链表反置（void reverse_list(List* l)函数），
然后，
通过比较反置后的链表最后一个元素和开始递增序列的第一个元素比较，如果小于，直接将原来递增链表连在其后即可
如果不小于，则在原来递增链表基础上，进行比较插入（void merge(List* l1, List* l2)函数）

以我的判断算法复杂度是O(m+n)，希望我没有算错吧，嘿嘿～

代码

#include<stdio.h>
#include<stdlib.h>

//默认l1是增序，l2是减序

typedef struct node
{
	int data;
	struct node * next;

}Node;

typedef struct list
{
	Node* head;
	Node* tail;

}List;


void print_list(List L)
{
	Node* p;
	p = L.head->next;

	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p -> next;
	}

	printf("\n");
}


void Init_list(List* L)
{
	Node* first = (Node*)malloc(sizeof(Node));
	if(!first)
		printf("wrong!\n");
	first -> data = 0;
	first -> next = NULL;
	L->head = L->tail = first;

	int length;

	printf("please enter list length: ");
	scanf("%d",&length); //scanf里面不能写类似于printf中打印字符串的语句
	for(int i = 0; i< length; i++)
	{
		Node* new = (Node*)malloc(sizeof(Node));
		scanf("%d",&new -> data); //这个语句注意一下

		new -> next = NULL;
		L->tail -> next = new;
		L->tail = new;

	}


}

void reverse_list(List* l)
{

	Node* prev; Node* pCur;
	prev = l -> head -> next;
	pCur = l -> head -> next -> next;//这两个节点的位置一定要确定好


	while(pCur != NULL)
	{
		prev -> next = pCur -> next;
		pCur -> next = l -> head -> next;
		l -> head -> next = pCur;
	
		//移动当前指针

		pCur = prev -> next;

	}
	

}


void merge(List* l1, List* l2)
{
	Node* p;
	Node* q;
	p = l2->head; q =l1->head;
	reverse_list(l2);
	if(p->next->data < q->next->data)
	{
		while(p -> next != NULL)
		{
			p = p -> next;
		}

		p -> next = q ->next;

		print_list(*l2);
	}
	//目前我能想到的就只有翻转l2后再进行合并
	//这样的时间复杂度貌似是O(m+n) 希望没有算错
	else
	{
		Node* prev;
		Node* pCur;
		Node* qCur;
		Node* save_temp;


		prev = l1->head;
		pCur = l1->head->next;
		qCur = l2->head->next;

		while(pCur && qCur)
		{
			if(pCur->data < qCur->data) //保留l2链表的当前比较元素的前驱结点
			{
				prev = pCur;
				pCur = prev -> next;
			}
			else
			{
				save_temp = qCur;
				qCur = qCur -> next;
				save_temp -> next = pCur;
				prev -> next = save_temp;
				prev = prev -> next;

			}


		}

		if(pCur)
			qCur = pCur;
		while(qCur != NULL)
		{
			prev -> next = qCur;
			qCur -> next = NULL;
			prev = qCur;
			qCur = qCur->next;
		}

		

		print_list(*l1);

	}

}




int main(int argc, char const *argv[])
{
	List l1,l2;
	Init_list(&l1);
	Init_list(&l2);

	merge(&l1,&l2);
	

	return 0;
}

运行截图：