反转链表-迭代反转法

反转链表，又可以称为翻转或逆置链表，如图： 

 常用的实现方案有 4 种，这里分别将它们称为迭代反转法、递归反转法、就地逆置法和头插法。值得一提的是，递归反转法更适用于反转不带头节点的链表；其它 3 种方法既能反转不带头节点的链表，也能反转带头节点的链表。

1、迭代反转链表：

      (1)思想：从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。
      (2)实现：借助 3 个指针分别命名为 beg、mid、end。它们的初始指向如图 所示：

        

接下来只需改变 mid 所指节点的指向即可，不用修改 3 个指针的指向。 

最后只需改变头结点指针的指向，另其和 mid 同向，就实现了链表的反转。

 

代码片段：

//迭代反转链表
link* iteration_reverse(link* p){
	if(p==NULL||p->next==NULL||p->next->next==NULL){
		return p;
	}
	else{
		link* beg=NULL;
		link* mid=p->next;
		link* end=p->next->next;
		while(1){
			//修改mid所指结点的指向
			mid->next=beg;
			//此时判断end是否为NULL，成立则退出循环
			if(end==NULL){
				break;
			} 
			//三个指针整体向后移
			beg=mid;
			mid=end;
			end=end->next; 
		}
		//最后修改头指针指向
		p->next=mid; 
		return p;
	}
} 

完整代码： 

#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));//创建头结点
	//头结点数据域为0 
	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=a;//temp指针向后移动 
	} 
	return p; 
}
//定义打印链表数据函数
void printLink(link* p){
	link*t=p->next;//定义指针变量指向首元结点 
	while(t){
		printf("%d ",t->elem);
		t=t->next;
	}
	printf("\n");
}

//迭代反转链表
link* iteration_reverse(link* p){
	if(p==NULL||p->next==NULL||p->next->next==NULL){
		return p;
	}
	else{
		link* beg=NULL;
		link* mid=p->next;
		link* end=p->next->next;
		while(1){
			//修改mid所指结点的指向
			mid->next=beg;
			//此时判断end是否为NULL，成立则退出循环
			if(end==NULL){
				break;
			} 
			//三个指针整体向后移
			beg=mid;
			mid=end;
			end=end->next; 
		}
		//最后修改头指针指向
		p->next=mid; 
		return p;
	}
} 

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

输出结果：

若无头结点：

 

代码片段：

//迭代反转法，head 为无头节点链表的头指针
link * iteration_reverse(link* head) {
	if (head == NULL || head->next == NULL) {
		return head;
	}
	else {
		link * beg = NULL;
		link * mid = head;
		link * end = head->next;
		//一直遍历
		while (1)
		{
			//修改 mid 所指节点的指向
			mid->next = beg;
			//此时判断 end 是否为 NULL，如果成立则退出循环
			if (end == NULL) {
				break;
			}
			//整体向后移动 3 个指针
			beg = mid;
			mid = end;
			end = end->next;
		}
		//最后修改 head 头指针的指向
		head = mid;
		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;
}
//迭代反转法，head 为无头节点链表的头指针
link * iteration_reverse(link* head) {
	if (head == NULL || head->next == NULL) {
		return head;
	}
	else {
		link * beg = NULL;
		link * mid = head;
		link * end = head->next;
		//一直遍历
		while (1)
		{
			//修改 mid 所指节点的指向
			mid->next = beg;
			//此时判断 end 是否为 NULL，如果成立则退出循环
			if (end == NULL) {
				break;
			}
			//整体向后移动 3 个指针
			beg = mid;
			mid = end;
			end = end->next;
		}
		//最后修改 head 头指针的指向
		head = mid;
		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 = NULL;
	//初始化链表（1，2，3，4）
	printf("初始链表为：\n");
	p = initLink();
	display(p);
	printf("反转链表为：\n");
	p = iteration_reverse(p);
	display(p);
	
	return 0;
}