C语言实现单链表逆置

小Bob来啦

发布于 2020-12-15 10:03:25

3.1K0

发布于 2020-12-15 10:03:25

文章被收录于专栏：用户8057608的专栏

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;
}

运行结果: