Reverse linked list - iterative inversion method

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

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

1、迭代反转链表：

      (1)思想：Start from the head node of the current linked list,一直遍历至链表的最后一个节点,这期间会逐个改变所遍历到的节点的指针域,另其指向前一个节点.
      (2)实现：借助 3 The pointers are named respectively beg、mid、end.它们的初始指向如图 所示：

        

Just change next mid 所指节点的指向即可,不用修改 3 个指针的指向. 

Finally, just change the pointer of the head node,另其和 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){
			//修改midPointer to the pointed-to node
			mid->next=beg;
			//此时判断end是否为NULL,If established, exit the loop
			if(end==NULL){
				break;
			} 
			//The three pointers move backward as a whole
			beg=mid;
			mid=end;
			end=end->next; 
		}
		//Finally modify the head pointer to point to
		p->next=mid; 
		return p;
	}
} 

完整代码： 

#include<stdio.h>
#include<stdlib.h>
//Define the linked list node structure 
typedef struct Link{
	int elem;
	struct Link* next;
}link;
//定义链表初始化函数 
link* initLink(){
	int i=0;
	link* temp=NULL;
	link* p=(link*)malloc(sizeof(link));//创建头结点
	//The header node data field is 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; 
}
//Define a function to print linked list data
void printLink(link* p){
	link*t=p->next;//Define a pointer variable to point to the first element node 
	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){
			//修改midPointer to the pointed-to node
			mid->next=beg;
			//此时判断end是否为NULL,If established, exit the loop
			if(end==NULL){
				break;
			} 
			//The three pointers move backward as a whole
			beg=mid;
			mid=end;
			end=end->next; 
		}
		//Finally modify the head pointer to point to
		p->next=mid; 
		return p;
	}
} 

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

输出结果：

If there is no head node：

 

代码片段：

//迭代反转法,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 established, exit the loop
			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 established, exit the loop
			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("Reverse the linked list as ：\n");
	p = iteration_reverse(p);
	display(p);
	
	return 0;
}