全球即时看！[数据结构]单向链表的翻转(C语言)

2022-12-27 21:12:31 来源：博客园

【资料图】

单向链表的翻转

单向链表翻转思路

假设链表是： 1->3->5->∅，所要求得的链表是 5->3->1->∅。只需要将每个节点的 next指向其之前的一个节点即可。对于第一个节点，如果是头节点不带数据的链表，那么只需要将其 next指向 head；如果头节点带数据，第一个节点的 next指向NULL。在进行操作过程中，我们用 pre标记之前的节点， cur标记当前的节点，当 cur指向的节点的 next指向前一个，那么就发了改变，所以同时我们还需要保存每个节点 cur的 next指向的节点，由此来往后进行操作。直到最后所有节点翻转结束，此时的 pre指针指向了当前完成翻转后链表的头，如果是有无数据头节点的链表，将其 head的 next指向当前的 pre即可。

单向链表翻转图解

cur指向第一个带数据节点，nex保存下一节点

cur的next指向前一个节点

此时头节点head应当指向第一个节点, 但是为了图解美观可以暂时不管它，后面也是这样

pre指向当前的cur, cur指向下一个节点

重复之前翻转的操作

此时cur指向了NULL, 退出循环

最后head接回, 其next指向当前pre指向的节点

单向链表翻转核心代码

void Reverse_Linklist(Linklist *head){    Linklist *cur = head->next;    Linklist *pre = NULL;    while(cur){Linklist *nex = cur->next;cur->next = pre;pre = cur;cur = nex;    }    head->next = pre;}

完整程序及测试

程序代码

#include #include #include typedef int Elemtype;typedef struct Node {    Elemtype data;           //结构体数据域    struct Node *next;       //结构体指针域} Linklist;Linklist* Initial_linklist(Linklist *mylist){    mylist = (Linklist *)malloc(sizeof(Linklist));    mylist->next = NULL;    return mylist;}//创建初始链表  尾插法void Create_linklist(Linklist *head, int n) {    //头节点(不带数据)    Linklist *node, *end;                        //普通节点 尾节点    end = head;                                  //当链表为空时 头尾指向同一个节点    printf("创建链表输入 %d 个元素:\n", n);    for (int i = 0; i < n; i++) {                //n为插入普通节点的个数node = (Linklist *)malloc(sizeof(Linklist));scanf("%d", &node->data);end->next = node;                        //之前的end的next指向了新的节点nodeend = node;                              //end往后移，此时新的节点变成尾节点    }    end->next = NULL;                            //end最后置NULL}//遍历输出链表void Show_linklist(Linklist *head) {    Linklist *node = head->next;    if (node == NULL)puts("链表为空");    while (node != NULL) {        printf("%d ", node->data);node = node->next;    }    printf("\n\n");}//翻转链表void Reverse_Linklist(Linklist *head){    Linklist *cur = head->next;    Linklist *pre = NULL;    while(cur){Linklist *nex = cur->next;cur->next = pre;pre = cur;cur = nex;    }    head->next = pre;}int main() {    //头指针初始化    Linklist *mylist;    mylist = Initial_linklist(mylist);    int n;    printf("输入创建初始链表元素个数: ");    scanf("%d", &n);    Create_linklist(mylist, n);    printf("初始状态链表:\n");    Show_linklist(mylist);    Reverse_Linklist(mylist);    printf("链表进行翻转后:\n");    Show_linklist(mylist);}