[数据结构与算法]C语言单向链表正向、反向、排序插入和链表逆转

一、链表定义

单向链表就像一根绳子一样，拿出来是一串，顺序表也是一串，但和单向链表不同，顺序表是连续存储的，不用管下一个节点位置在哪，反正就在后面，而单向链表在内存中是不连续存储的，看到有坑就放进去，然后还得保存放置的地址。所以，定义单向链表就是定义一个结构体，结构体里有两个成员，一个是要保存的数据，一个是下一个节点的地址。

typedef struct NODE{
	int data;
	struct NODE *next;
}NODE,*NEXT;

我这里用typedef取别名取了一个结构体和结构体指针，定义的这个结构体NODE其实没什么作用，主要是开辟内存的时候malloc函数要传入一个整数，用sizeof求NODE需要要多大的字节然后传入到malloc中获得一个节点的空间。

二、初始化链表

初始化一个链表，就先初始化链表的头，有头才能有后面的节点。

    int temp;
	NEXT node = NULL;
	node = GetNewNode();
	scanf("%d",&temp);
	getchar();
	node->data = temp;

这里定义了一个temp变量，用来获取从键盘中输入的数据，定义一个指针node先指向NULL，然后获取一个节点的内存并返回给node，最后通过键盘输入获取数据赋值给data，第一个节点就算完成了。
getNewNode函数

NEXT GetNewNode(){
	NEXT node = malloc(sizeof(NODE));
	node->next = NULL;//先让该节点的下一个节点为空
	return node;
}

三、输入链表

初始化完成后，就开始从键盘中一个一个输入节点的数据了，这里就要用的while循环了，因为我这里数据定义的是int型的，所以我加了一个跳出循环的条件，就是输入非数字的时候跳出循环，结束输入。
具体代码如下：

while(1){
		NEXT next = GetNewNode();
		if(scanf("%d",&temp)==1){
			getchar();
		    next->data = temp;
		    InsertNodeLast(node,next);//新节点插入到旧节点后面
		    ShowNode(node);
		}else{
			printf("停止输入");
		    break;	}
	}

原理就是先获取一个新节点内存，然后给新节点赋值，然后让新节点插到旧节点后面，最后输出该链表所有内容。
其中注意的点：如果scanf其实是有返回值的，如果返回值为1就是输入的数字，还有，scanf停止输入的条件是用户按了回车键，也就是输入了换行符“\n”就会停止从输入缓冲区中读取数据，但是换行符会一直存在输入缓冲区不会被丢弃，影响下一次的输入，所以可以使用getchar把换行符从输入缓冲区给拿出来。
下面给出InsertNodeLast函数代码

void InsertNodeLast(NEXT old,NEXT new){
	while(old->next!=NULL){//遍历链表，直到到最后一个节点
		old = old->next;
	}
	old -> next = new;
	new->next = NULL;
}

ShowNode函数

void ShowNode(NEXT node){
	while(node->next!=NULL){
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t",node->data);//跳出循环的时候其实还有最后一个节点没输出
	printf("\n");
}

四、反向、排序插入和逆转

1、反向插入
反向插入就是创建一个节点让它插在链表的最前面，当头结点。
我的实现方法就是：把新节点的值和原来头节点的值进行互换，然后让原来头结点指向新节点，让新节点指向原来头结点的下一个节点，这样就算插入到第一个了。
原理图大概就是这个样子。

给出实现代码：

//从前面插入
void InsertNodeFirst(NEXT old,NEXT new){
	int temp = old->data;
	old->data = new->data;
	new->data = temp;
	new->next = old->next;
	old->next = new;
}

2、排序插入
我这里实现的是按从小到大排序，从大到小排序可以看完之后自己去设计。
原理主要是三种情况，将新节点的数据与链表中的数据进行逐一比较，
①比第一个节点数据还小，那就直接插到最前面；
②比最后一个数据还大，那就直接插到最后面；
③中间值，那就先找到一个比他小的节点，然后判断该节点的后面的一个节点是否比新节点大，如果满足就插在两个节点中间，不满足继续遍历。
这里给出第三种情况的示意图

给出该函数完整代码：

//从小到大排序
int InsertNodeSort(NEXT old,NEXT new){
	NEXT f = old;
	if(old->next==NULL){//如果是第二个节点
		if(old->data>new->data)//如果小于第一个节点就插到前面
			InsertNodeFirst(old,new);
		else
			InsertNodeLast(old,new);//否则插到后面
	}else{
		while(old->next!=NULL){//如果要插入的不是第二个节点
			if(f->data>new->data){//先判断是否第一个节点大于新节点
				int temp = old->data;
				old->data = new->data;
				new->data = temp;
				new->next = old->next;
				old->next = new;
				return 1;//跳出循环
			}else if(old->data<=new->data){//如果节点小于或等于新节点
				NEXT n = old->next;//该节点的下一个节点
				if(n->data>new->data||n == NULL){//判断下一个节点是否大于新节点
					old->next = new;//大于就插到该节点和下一个节点之间
					new->next = n;
					return 1;//跳出循环，插入结束
				}
			}
			old = old->next;
	    }
	    old->next = new;
	    new->next = NULL;
	}
	return 1;
}

这里的返回值没什么意义，主要是用来结束函数执行，break只能跳出循环，return是跳出整个函数。
3、链表逆转
这个功能真得写了我很久很久，试了很多种方法，一直都是失败的，最终想到一种很简单的方法，原理简单概括就是：将头结点的后面的节点一个一个往前面移动，最终返回最后移到前面的节点的地址，赋值给原来的头节点。
原理图：

画得不太清除，因为有些东西真的是只能意会不能言传。
给出代码帮助理解：

//翻转
NEXT ReverseNode(NEXT node){
	NEXT nodes = node ->next;
	NEXT temp = node;//定义一个指针始终指在链表最前面
	NEXT rt;
	while(node->next!=NULL){
		node->next = nodes->next;
		nodes->next = temp;//指向最前面的节点
		temp = nodes;//将最前面的节点再赋值给temp
		rt = temp;//temp作为返回值
		nodes = node ->next;
	}
	return rt;
}

五、总结

其实只要理解链表的结构，不管怎么插入或者怎么输出都能写出算法，最后给出完整代码，不理解可以私信或者评论。

#include<stdio.h>
#include<stdlib.h>
typedef struct NODE{
	int data;
	struct NODE *next;
}NODE,*NEXT;
NEXT GetNewNode(){
	NEXT node = malloc(sizeof(NODE));
	node->next = NULL;
	return node;
}
//从前面插入
void InsertNodeFirst(NEXT old,NEXT new){
	int temp = old->data;
	old->data = new->data;
	new->data = temp;
	new->next = old->next;
	old->next = new;
}
//从后面插入
void InsertNodeLast(NEXT old,NEXT new){
	while(old->next!=NULL){//遍历链表，直到到最后一个节点
		old = old->next;
	}
	old -> next = new;
	new->next = NULL;
}
//从小到大排序
int InsertNodeSort(NEXT old,NEXT new){
	NEXT f = old;
	if(old->next==NULL){//如果是第二个节点
		if(old->data>new->data)//如果小于第一个节点就插到前面
			InsertNodeFirst(old,new);
		else
			InsertNodeLast(old,new);//否则插到后面
	}else{
		while(old->next!=NULL){//如果要插入的不是第二个节点
			if(f->data>new->data){//先判断是否第一个节点大于新节点
				int temp = old->data;
				old->data = new->data;
				new->data = temp;
				new->next = old->next;
				old->next = new;
				return 1;//跳出循环
			}else if(old->data<=new->data){//如果节点小于或等于新节点
				NEXT n = old->next;//该节点的下一个节点
				if(n->data>new->data||n == NULL){//判断下一个节点是否大于新节点
					old->next = new;//大于就插到该节点和下一个节点之间
					new->next = n;
					return 1;//跳出循环，插入结束
				}

			}
			old = old->next;
	    }
	    old->next = new;
	    new->next = NULL;

	}
	return 1;
	
}
//翻转
NEXT ReverseNode(NEXT node){
	NEXT nodes = node ->next;
	NEXT temp = node;//定义一个指针始终指在链表最前面
	NEXT rt;
	while(node->next!=NULL){
		node->next = nodes->next;
		nodes->next = temp;//指向最前面的节点
		temp = nodes;//将最前面的节点再赋值给temp
		rt = temp;//temp作为返回值
		nodes = node ->next;

	}
	return rt;
}

void ShowNode(NEXT node){
	while(node->next!=NULL){
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t",node->data);
	printf("\n");
}
int main(){
	int temp;
	NEXT node = NULL;
	node = GetNewNode();
	scanf("%d",&temp);
	getchar();
	node->data = temp;
	ShowNode(node);
	while(1){
		NEXT next = GetNewNode();
		if(scanf("%d",&temp)==1){
			getchar();
		    next->data = temp;
		    InsertNodeLast(node,next);//调用不同方法插入方式不同
		    ShowNode(node);
		}else{
		    break;	}
	}
	ShowNode(node);
	node = ReverseNode(node);
	ShowNode(node);
	return 0;
}