C语言实现单链表的逆置

╰半夏微凉° 2022-03-22 03:16 252阅读 0赞

**单链表的逆置是一个非常经典的问题，这里利用两个思想进行解决。**

**首先，我们需要看下原理图，其实两个思想都是一样的，都是使后一个的节点的 next 指针指向前一个节点，依次递推，直到第二个节点指向第一个节点，第一个节点的 next 指针指向 NULL。**

**![SouthEast][]**

**第一种方法：**

**在链表往前走的过程中，记录前一个节点，当前节点和后一个节点，并使当前节点的 next 指针指向前一个节点，直到最后一个节点指向倒数第二个节点**

**算法实现如下：**

void reverse_list(LinkList list){ LinkedNode *pre = list; LinkedNode *cur = list->next; LinkedNode *next = NULL; if(list == NULL || list->next == NULL)  return;  /*在这里实现翻转*/ while(cur != NULL) {  next = cur->next;  cur->next = pre;  pre = cur;  cur = next; } list->next = NULL; list = pre; print(list); return;}

**第二种方法**

**这里利用递归的思想，首先完成最后一个节点指向倒数第二个，再使倒数第二个指向倒数第三个，。。。直到第二个指向第一个节点，第一个节点指向 NULL，思想和第一种方法正好是相反的**

**算法实现如下：**

void reverse_the_list(LinkedNode *cur, LinkList *list){ LinkedNode *next = NULL; if(cur == NULL || cur->next == NULL) {  *list = cur; } else {  next = cur->next;  reverse_the_list(next, list);  next->next = cur;  cur->next = NULL; } return;}

**下面给出完整的实现和实验结果：**

#include <stdio.h>#include <malloc.h>typedef int DataType;typedef struct node{
          DataType data; struct node *next;}LinkedNode, *LinkList;LinkList create_list(){ DataType value[] = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int len = sizeof(value) / sizeof(DataType); int i = 0; LinkedNode *list_head = NULL; LinkedNode *temp = NULL; LinkedNode *p = NULL; list_head = (LinkedNode*)malloc(sizeof(LinkedNode)); list_head->data = value[0]; list_head->next = NULL; temp = list_head; for(i = 1; i < len; i++) {  while (temp->next != NULL)    {     temp = temp->next;    }    p = (LinkedNode*)malloc(sizeof(LinkedNode));  p->data = value[i];  p->next = NULL;  temp->next = p; } return list_head;}/*打印链表中的各个节点*/void print(LinkList list){ LinkedNode *temp = NULL; if(list == NULL)  return;  temp = list; while(temp != NULL) {  printf("%d  ", temp->data);  temp = temp->next; } printf("\n"); return;}void reverse_list(LinkList list){ LinkedNode *pre = list; LinkedNode *cur = list->next; LinkedNode *next = NULL; if(list == NULL || list->next == NULL)  return;  /*在这里实现翻转*/ while(cur != NULL) {  next = cur->next;  cur->next = pre;  pre = cur;  cur = next; } list->next = NULL; list = pre; print(list); return;}void reverse_the_list(LinkedNode *cur, LinkList *list){ LinkedNode *next = NULL; if(cur == NULL || cur->next == NULL) {  *list = cur; } else {  next = cur->next;  reverse_the_list(next, list);  next->next = cur;  cur->next = NULL; } return;}int main(){ LinkList list = NULL; LinkedNode *temp = NULL; LinkList list2 = NULL; list = create_list(); print(list); reverse_list(list); list2 = create_list(); temp = list2; reverse_the_list(temp, &list2); print(list2); return 0;}

**运行结果如下所示：**

**![SouthEast 1][]**

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[SouthEast]: /images/20220322/c31f235c12aa4d59b8e12b6a4d76cc10.png
[SouthEast 1]: /images/20220322/01a899a093bb4fddbc934b0bf11b1669.png
[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485