C语言实现单链表逆置

2020年05月28日 22:30 __ _ _ _ _

文章配图

Life is either a daring adventure or nothing at all。生活要么大胆尝试，要么什么都不是。

学完C语言你会发现真的不难，可能就指针有点绕，其余的都是小打小闹。链表是数据结构里的内容，数据结构和算法是程序设计的核心，也是学IT这行必须掌握的内容。

如下此题其实还有别的方法,比如用数组存储链表中的数据,需要注意的是数组小标要准确.

任务描述

本关需要你设计一个程序，实现单链表的逆置。

单链表的逆置有两种方法：头插法和就地逆置法，这两种方法虽然都有逆置的效果，但还是有着不小的差别。

头插法

逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

就地逆置法

先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点。

**输入：61 212 7 8 0 2 输出： **

链表逆置前的数据:1 212 7 8 0 2

链表逆置后的数据:2 0 8 7 212 1

源代码：

#include <stdio.h>#include <stdlib.h>typedef struct node {    int data;    struct node *next;}Node;//创建链表Node *CreatList(void){    int val, i, n;    Node *phead, *p, *q;    phead = NULL;    scanf("%d", &n);    for(i=0; i<n; ++i)    {        scanf("%d", &val);        p = (Node *)malloc(sizeof(Node));        p->data = val;        if(NULL == phead)            q = phead = p;        else            q->next = p;        q = p;    }    p->next = NULL;    return phead;}//链表的逆置Node *ReverseList(Node *phead){    Node *p, *q, *r;    p = phead;    q=r=NULL;    while(p)    {        q = p->next;        p->next = r;        r = p;        p = q;    }    return r;}//输出链表void ShowList(Node *phead){    Node *p;    p = phead;    while(p)    {        printf("%d ", p->data);        p = p->next;    }    printf("\n");}int main(void){    Node *phead;    phead = CreatList();    printf("链表逆置前的数据:\n");    ShowList(phead);    phead = ReverseList(phead);    printf("链表逆置后的数据:\n");    ShowList(phead);    return 0;}

运行结果:

文章配图