MENU

就地逆置单链表

• October 26, 2020 •

编写算法实现带头结点单链表seqlist的就地逆置,即利用原带头结点单链表seqlist的结点空间,把数据元素顺序排反


题目分析:

在前面2-18讲了顺序表的就地逆置,但单链表的就地逆置与顺序表有所不同,因为顺序表可以根据下标值直接快速的找到对应的数据,而单链表只能从头结点一个一个的遍历才能找到相应数据元素,所以逆置单链表不采用第一个结点和最后一个结点交换的方式。那怎么做呢?

既然都讲到这里了,咱就先来讨论讨论单链表的两种建立方式————头插法和尾插法

利用尾插法建立的单链表数据是顺序的,用头插法建立的单链表数据是逆序的

例如:用数列 2,4,6,8,10,12六个数字来建立单链表

如果利用尾插法,得到的链表是这样的:2,4,6,8,10,12
用头插法,得到的链表是这样的:12,10,8,6,4,2
Are you understand?
接下来咱来分析分析为什么是这样的



下面给出头插法和尾插法的代码:

/*尾插法建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(Node *head, dataType arr[], int n)
{
    Node *p = head;                       //新增一个指针,用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次,每次循环都在链表尾部追加一个结点
    {
        Node *q = (Node*)malloc(sizeof(Node));//新建立结点,并为之分配内存空间
        q->data = arr[i];                 //数据域赋值,将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q,从此q成为最后一个结点,原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点,为下一次尾部插入做准备
    }
}
/*头插法建立单链表——得到的链表是逆序的
利用数组的前n个数建立一条单链表*/
void listBuildHead(Node *head,dataType arr[],int n)
{
    for(int i = 0;i < n;i++)
    {
        Node *q = (Node*)malloc(sizeof(Node));
        q->data = arr[i];
        q->next = head->next;              //紧跟头结点后面插入数据结点
        head->next = q;
    }
 }

尾插法和头插法的补充知识就到这里了,我们再来看这道题

尾插法是顺序的,头插法是逆序的,这题要我们就地逆置,也就是完成逆序,毫无疑问我们会想到头插法,所以我们的解题思路就是,在遍历链表的同时,利用头插法一个一个再建立新的链表

请看下图》》》》》》》》》》》》》


代码实现:

#include<stdio.h>
#include<stdlib.h>
typedef int dataType;    //数据类型为int
//结点结构体
typedef struct node
{
    dataType data;      //数据域
    struct node *next;  //指针域
}Node;
//初始化结点
void listInitiate(Node **head)            //双星指针,地址的地址,在初始化时,我们要使地址的值改变,所以使用双星作为参数传入
{
    *head = (Node*)malloc(sizeof(Node));  //为头结点分配位置空间(一个结点的大小)
    (*head)->next = NULL;                 //头结点指针域初始默认为空
}
/*尾插法建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(Node *head, dataType arr[], int n)
{
    Node *p = head;                       //新增一个指针,用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次,每次循环都在链表尾部追加一个结点
    {
        Node *q = (Node*)malloc(sizeof(Node));//新建立结点,并为之分配内存空间
        q->data = arr[i];                 //数据域赋值,将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q,从此q成为最后一个结点,原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点,为下一次尾部插入做准备
    }
}
//遍历输出函数
void listPrint(Node *head)
{
    printf("单链表:");
    Node *p = head;                       //新增一个指针,用来代替head指针
    while (p->next != NULL)
    {
        printf("%d   ", p->next->data);
        p = p->next;                      //这一句不要忘了,不然会死循环的,我总是忘掉这一句
    }
    printf("\n");
}
//就地逆置函数
void listReserve(Node* head)
{
    if (head == NULL || head->next == NULL || head->next->next == NULL) //如果单链表为空、只有一个结点,本身就是逆序
        return;
    Node* p = head->next->next;           //将链表的第一个结点给一个指针p,以免丢失数据
    head->next->next = NULL;              //将第一个结点和第二个结点分开
    while (p != NULL)                     //遍历链表
    {
        Node* q = p->next;
        p->next = head->next;
        head->next = p;                   //在头结点的前面插入新的结点
        p = q;                            //为下一次插入做准备
    }
}
int main()
{
    Node link1;
    Node *p;
    dataType arr[] = {2,4,6,8,10,12,14};
    p = &link1;
    listInitiate(&p);
    listBuildRear(p,arr,7);      //利用数组arr的前七个数据建立一条链表
    printf("原");
    listPrint(p);                //打印原链表
    printf("就地逆置之后的");
    listReserve(p);              //打印逆置后的链表
    listPrint(p);
    return 0;
}

运行结果:


代码编译器:Dev-C++
ok,完美解决

Last Modified: November 12, 2020
Archives QR Code Tip
QR Code for this page
Tipping QR Code