【资料图】

单向链表的翻转

单向链表翻转 思路

假设链表是： 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);}

运行结果

推荐内容