反转链表-头插反转法

        （1）思想：是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

        （2）实现（如下图）：

一开始创建一个新的头结点，然后在创建一个temp指针。

	link * new_head = (link*)malloc(sizeof(link));
	new_head->elem = 0;
	new_head->next = NULL;
	link * temp = NULL;

 下一步将摘除掉原链表中的结点：

temp = head->next;
//将 temp 从 head 中摘除
head->next = head->next->next;

进行新链表的头部插入： 

//将 temp 插入到 new_head 的头部
temp->next = new_head->next;
new_head->next = temp;

 

 以此类推：

摘除2：

temp = head->next;

head->next = head->next->next;

 

 插入2：

temp->next = new_head->next;

new_head->next = temp;

 

 

 插入完成：

 摘除3：

 

插入3：

 摘除4：

（标志循环结束） 

插入4：

 插入END。

片段代码：

//头插法反转链表
link * head_reverse(link * head) {
	//为新节点添加头节点
	link * new_head = (link*)malloc(sizeof(link));
	new_head->elem = 0;
	new_head->next = NULL;
	link * temp = NULL;
	if (head == NULL || head->next == NULL || head->next->next == NULL ) {
		return head;
	}
	while (head->next != NULL)
	{
		temp = head->next;
		//将 temp 从 head 中摘除
		head->next = head->next->next;

		//将 temp 插入到 new_head 的头部
		temp->next = new_head->next;
		new_head->next = temp;
	}
	return new_head;
}

完整代码：

 

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

typedef struct Link{
	int elem;
	struct Link* next;
}link;

link * initLink() {
	int i = 0;
	link * temp = NULL;
	link * p = (link*)malloc(sizeof(link));//创建头节点
	//首元节点先初始化
	p->elem = 0;
	p->next = NULL;
	temp = p;//头指针指向头节点
	for (i = 1; i < 5; i++) {
		link *a = (link*)malloc(sizeof(link));
		a->elem = i;
		a->next = NULL;
		temp->next = a;
		temp = temp->next;
	}
	return p;
}

void display(link *p) {
	link* temp = p->next;//将temp指针重新指向首元结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while (temp) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}
//头插法反转链表
link * head_reverse(link * head) {
	//为新节点添加头节点
	link * new_head = (link*)malloc(sizeof(link));
	new_head->elem = 0;
	new_head->next = NULL;
	link * temp = NULL;
	if (head == NULL || head->next == NULL || head->next->next == NULL ) {
		return head;
	}
	while (head->next != NULL)
	{
		temp = head->next;
		//将 temp 从 head 中摘除
		head->next = head->next->next;

		//将 temp 插入到 new_head 的头部
		temp->next = new_head->next;
		new_head->next = temp;
	}
	return new_head;
}

int main()
{
	link*p=initLink();
	printf("原始链表：");
	display(p);
	printf("反转链表：");
	p=head_reverse(p); 
	display(p);
	return 0;
} 

输出结果：

若无头结点：

 

代码片段：

//头插法反转链表
link * head_reverse(link * head) {
	link * new_head = NULL;
	link * temp = NULL;
	if (head == NULL || head->next == NULL) {
		return head;
	}
	while (head != NULL)
	{
		temp = head;
		//将 temp 从 head 中摘除
		head = head->next;

		//将 temp 插入到 new_head 的头部
		temp->next = new_head;
		new_head = temp;
	}
	return new_head;
}

完整代码：

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

typedef struct Link{
	int elem;
	struct Link* next;
}link;

link * initLink() {
	int i;
	link * p = NULL;//创建头指针
	link * temp = (link*)malloc(sizeof(link));//创建首元节点
	//首元节点先初始化
	temp->elem = 1;
	temp->next = NULL;
	p = temp;//头指针指向首元节点
	for (i = 2; i < 5; i++) {
		link *a = (link*)malloc(sizeof(link));
		a->elem = i;
		a->next = NULL;
		temp->next = a;
		temp = temp->next;
	}
	return p;
}
void display(link *p) {
	link* temp = p;//将temp指针重新指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while (temp) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}
//头插法反转链表
link * head_reverse(link * head) {
	link * new_head = NULL;
	link * temp = NULL;
	if (head == NULL || head->next == NULL) {
		return head;
	}
	while (head != NULL)
	{
		temp = head;
		//将 temp 从 head 中摘除
		head = head->next;

		//将 temp 插入到 new_head 的头部
		temp->next = new_head;
		new_head = temp;
	}
	return new_head;
}

int main()
{
	link*p=initLink();
	printf("原始链表：");
	display(p);
	printf("反转链表：");
	p=head_reverse(p); 
	display(p);
	return 0;
}