反转链表（迭代及递归实现）

从上图中可以看出，反转一个链表只需要改变Node.link。

I. 迭代实现

思路

设置三个结构体指针Prev、current、next，分别保存之前的节点的地址、目前的节点地址、之后的节点地址。

代码实现

void Reverse(){
    struct Node *current, *prev, *next;
    current = head;
    prev = NULL;
    while(current != NULL){
        next = current->next;//next 用来存储当前Node的next，当Node.next被prev覆盖后，next将值赋 给current从而进入下一个循环。
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Insert(int n){
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = n;
	temp->next = NULL;
	struct Node* temp1 = head;
	if(head == NULL){
		head = temp;
		return;
	}
	while(temp1->next != NULL){
		temp1 = temp1->next;
	}
	temp1->next = temp;
}
void Print(){
	struct Node* temp = head;
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void Reverse(){
    struct Node *current, *prev, *next;
    current = head;
    prev = NULL;
    while(current != NULL){
        next = current->next;//next 用来存储当前Node的next，当Node.next被prev覆盖后，next将值赋                                       给current从而进入下一个循环。
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}
int main(){
	head = NULL;
	Insert(2);
	Insert(4);
	Insert(6);
	Insert(5);
	Print();
	Reverse();
	Print();
	return 0;
}

输出结果：

2 4 6 5
5 6 4 2

II. 递归实现

1）递归实现输出的反转

我们先写一个递归形式的Print函数，因为递归需要给函数传参，因此函数形式为Print(struct Node* p)。

void Print(struct Node* p){//p初始为头节点的地址
    if(p == NULL){
        printf("\n");
        return;
    }
    printf("%d ",p->data);
    Print(p->next);
}

此时总是先输出再调用函数自身，因此是正向输出。如果我们将printf与Print两行代码交换位置，即

void Print(struct Node* p){//p初始为头节点的地址
    if(p == NULL) return;
    Print(p->next);
    printf("%d ",p->data);
}

那么函数会在输出之前先进行重复调用，进行到递归结束条件后，依次执行输出。

完整代码如下

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Insert(int n){
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = n;
	temp->next = NULL;
	struct Node* temp1 = head;
	if(head == NULL){
		head = temp;
		return;
	}
	while(temp1->next != NULL){
		temp1 = temp1->next;
	}
	temp1->next = temp;
}
void Print(){
	struct Node* temp = head;
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void ReversePrint(struct Node* p){//p初始为头节点的地址
    if(p == NULL) return;
    ReversePrint(p->next);
    printf("%d ",p->data);
}
int main(){
	head = NULL;
	Insert(2);
	Insert(4);
	Insert(6);
	Insert(5);	
	Print();
	ReversePrint(head);
	return 0;
}

输出结果

2 4 6 5
5 6 4 2

2）递归实现链表反转

反转输出并没有实现链表的反转，因为head、next的值都没有发生改变。但是我们依然可以采用递归的方式实现链表的反转。

设计一个Reverse函数，使得其能够以递归方式实现链表反转。

void Reverse(struct Node* p){//p初始为头节点的地址
    if(p->next == NULL){
    	head = p;
    	return;
	}
	Reverse(p->next);
	struct Node* q = p->next;
	q->next = p;//也可以简洁地表示为p->next->next = p
	p->next = NULL;
}

完整代码如下

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Insert(int n){
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = n;
	temp->next = NULL;
	struct Node* temp1 = head;
	if(head == NULL){
		head = temp;
		return;
	}
	while(temp1->next != NULL){
		temp1 = temp1->next;
	}
	temp1->next = temp;
}
void Print(){
	struct Node* temp = head;
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void Reverse(struct Node* p){//p初始为头节点的地址
    if(p->next == NULL){
    	head = p;
    	return;
	}
	Reverse(p->next);
	struct Node* q = p->next;
	q->next = p;
	p->next = NULL;
}
int main(){
	head = NULL;
	Insert(2);
	Insert(4);
	Insert(6);
	Insert(5);	
	Print();
	Reverse(head);
	Print();
	return 0;
}