从上图中可以看出,反转一个链表只需要改变Node.link。
I. 迭代实现
思路
设置三个结构体指针Prev、current、next,分别保存之前的节点的地址、目前的节点地址、之后的节点地址。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12
| void Reverse(){ struct Node *current, *prev, *next; current = head; prev = NULL; while(current != NULL){ next = current->next; current->next = prev; prev = current; current = next; } head = prev; }
|
完整代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #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; 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; }
|
输出结果:
II. 递归实现
1)递归实现输出的反转
我们先写一个递归形式的Print函数,因为递归需要给函数传参,因此函数形式为Print(struct Node* p)。
1 2 3 4 5 6 7 8
| void Print(struct Node* p){ if(p == NULL){ printf("\n"); return; } printf("%d ",p->data); Print(p->next); }
|
此时总是先输出再调用函数自身,因此是正向输出。如果我们将printf与Print两行代码交换位置,即
1 2 3 4 5
| void Print(struct Node* p){ if(p == NULL) return; Print(p->next); printf("%d ",p->data); }
|
那么函数会在输出之前先进行重复调用,进行到递归结束条件后,依次执行输出。
完整代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #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){ 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)递归实现链表反转
反转输出并没有实现链表的反转,因为head、next的值都没有发生改变。但是我们依然可以采用递归的方式实现链表的反转。
设计一个Reverse函数,使得其能够以递归方式实现链表反转。
1 2 3 4 5 6 7 8 9 10
| void Reverse(struct Node* p){ if(p->next == NULL){ head = p; return; } Reverse(p->next); struct Node* q = p->next; q->next = p; p->next = NULL; }
|
完整代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #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){ 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; }
|