[数据结构与算法]C语言单链表的创建反转与合并

//不采用封装的单链表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
typedef int DATA;

typedef struct Node                              //创建节点的结构
{
	DATA data;
	struct Node *next;
}NODE ,*LPNODE;

LPNODE createList()                               //创建初始化链表的模板
{
	LPNODE HeadNode = (LPNODE)malloc(sizeof(NODE));//创建头节点
	assert(HeadNode);                              //判定是否创建成功，不成功则assert函数结束程序抛出异常位置
	HeadNode->next = NULL;                         //头节点下一个置空
	return HeadNode;                               //返回头节点地址
}

LPNODE createNode(DATA data)                      //创建节点的模型
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));//创建节点
	assert(newNode);                              //对节点属性的操作
	newNode->data = data;
	newNode->next = NULL;
	return newNode;                               //返回节点地址
}

void printfList(struct Node * list)
{
	LPNODE pmove = list->next;                   //建立临时指针指向头节点地址 
	while (pmove != NULL)
	{
		printf("%d\t",pmove->data);              //输出节点的数据
		pmove = pmove->next;                     //指针后移
	}
	printf("\n");
}

void push_sort(struct Node * list, DATA data)     //入栈
{
	LPNODE newNode = createNode(data);
	LPNODE proNode = list;
	LPNODE curNode = list->next;
	while (curNode != NULL&&curNode->data <= data)
	{
		proNode = curNode;
		curNode = curNode->next;
	}
	if (curNode == NULL&&proNode == list)
	{
		list->next = newNode;                  //头插法，不断将list->next指向现在的新节点
	}
	else if (curNode == NULL&&proNode != list)
	{
		proNode->next = newNode;
	}
	else
	{
		proNode->next = newNode;
		newNode->next = curNode;
	}
}

void reverse(LPNODE list)              //反转
{
	//链表空，或者只有一个节点
	if (list == NULL||list->next == NULL || list->next->next == NULL)
	{
		return;
	}
	LPNODE proNode = NULL;
	LPNODE curNode = list->next;                   //curNode指向现在的节点
	LPNODE surList = curNode->next;                //surList指向现节点的下一个节点
	while (surList != NULL)
	{
		//当前节点的下一个节点的值置为临时指针的值，临时指针的值修改为当前节点的值
		curNode->next = proNode;                   
		proNode = curNode;          

		//当前节点的值修改为当前节点下一个的值surNodew，surNode再次获取新的当前节点下一个的值
 		curNode = surList;                         
		surList = curNode->next;
	}
	//当前节点下一个的值修改为临时指针存放的之前的当前节点的值
	curNode->next = proNode;
	list->next = curNode;
}

void mergeList(LPNODE list1, LPNODE list2)
{
	LPNODE pmove = list2->next;
	while (pmove != NULL)
	{
		push_sort(list1, pmove->data);//将list2的数据插入list1，当有序链表进行合并等，链表会进行自动冒泡排序
		pmove = pmove->next;
	}
}

int main()
{
	srand((unsigned int)time(NULL));
	LPNODE list = createList();
	for (int i = 0; i <= 10; i++)
	{
		push_sort(list, rand()%100);
	}
	printfList(list);

	reverse(list);
	printfList(list);

	LPNODE list1 = createList();
	push_sort(list1, 7);
	push_sort(list1, 5);
	push_sort(list1, 3);
	LPNODE list2 = createList();
	push_sort(list2, 2);
	push_sort(list2, 4);
	push_sort(list2, 6);
	mergeList(list1, list2);
	printfList(list1);
}