反转链表-就地逆置法

（1）思想：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。

（2）实现：在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）。

 

 

 

 

 

 

END

代码片段:

//就地逆置法
link * local_reverse(link * head) {
	link * beg = NULL;
	link * end = NULL;
	if (head == NULL || head->next == NULL || head->next->next == NULL) {
		return head;
	}
	beg = head->next;
	end = head->next->next;
	while (end != NULL) {
		//将 end 从链表中摘除
		beg->next = end->next;
		//将 end 移动至链表头
		end->next = head->next;
		head->next = end;
		//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
		end = beg->next;
	}
	return 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;
}
//就地逆置法
link * local_reverse(link * head) {
	link * beg = NULL;
	link * end = NULL;
	if (head == NULL || head->next == NULL || head->next->next == NULL) {
		return head;
	}
	beg = head->next;
	end = head->next->next;
	while (end != NULL) {
		//将 end 从链表中摘除
		beg->next = end->next;
		//将 end 移动至链表头
		end->next = head->next;
		head->next = end;
		//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
		end = beg->next;
	}
	return head;
}

void display(link *p) {
	link* temp = p->next;//将temp指针重新指向首元结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while (temp) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}
int main()
{
	link*p=initLink();
	printf("原始链表：");
	display(p);
	printf("反转链表：");
	p=local_reverse(p); 
	display(p);
	return 0;
} 

输出结果：

若无头结点：

 

 

代码片段：

 

//就地逆置法
link * local_reverse(link * head) {
	link * beg = NULL;
	link * end = NULL;
	if (head == NULL || head->next == NULL) {
		return head;
	}
	beg = head;
	end = head->next;
	while (end != NULL) {
		//将 end 从链表中摘除
		beg->next = end->next;
		//将 end 移动至链表头
		end->next = head;
		head = end;
		//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
		end = beg->next;
	}
	return 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;
}
//就地逆置法
link * local_reverse(link * head) {
	link * beg = NULL;
	link * end = NULL;
	if (head == NULL || head->next == NULL) {
		return head;
	}
	beg = head;
	end = head->next;
	while (end != NULL) {
		//将 end 从链表中摘除
		beg->next = end->next;
		//将 end 移动至链表头
		end->next = head;
		head = end;
		//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
		end = beg->next;
	}
	return head;
}

void display(link *p) {
	link* temp = p;//将temp指针重新指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while (temp) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}
int main()
{
	link*p=initLink();
	printf("原始链表：");
	display(p);
	printf("反转链表：");
	p=local_reverse(p); 
	display(p);
	return 0;
}