试写一算法，对单链表进行逆置

2022-11-01 15:57:08

NOTICE: 本篇代码是按照源码的书写顺序所写，复制之后可直接运行。

环境： vscode

题目：

试写一算法，对单链表进行逆置

分析：

单链表的逆置需要设置两个指针，第一个进行遍历单链表；第二个进行节点的反向连接。

单链表的逆置其实就是反复利用删除和插入操作。

主意：本题所说的逆置不能开辟新的内存空间，这样一来就不能创建一个新的表然后利用尾插法进行“逆置”了。

代码：

初始化单链表：

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

Status InitList(LinkList &L)
{   // 初始化单链表 L
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;

    return OK;
}//InitList

生成单链表：

Status CreateList(LinkList &L, int e)
{   // 创建单链表 L
    LinkList p = L;
    while(p->next)
        p = p->next;
    LinkList temp = (LinkList)malloc(sizeof(LNode));
    temp->data = e;
    temp->next = NULL;
    p->next = temp;

    return OK;
}//CreateList

打印单链表：

Status DispList(LinkList &L)
{   // 打印单链表 L
    LinkList p = L->next;
    while(p)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    return OK;
}//DispList

逆置：

Status ListOppose(LinkList &L)
{   // 将带表头节点的单链表逆置
    LinkList q, p, s;
    p = L;
    p = p->next;
    L->next = NULL;
    while(p) // 因为 while 中有 p = p->next 所以终止条件不用写成 p->next
    {
        q = p;
        p = p->next;
        q->next = L->next; // q 节点指向现在的 L 的首元结点。这一行加上下一行相当于一个插入操作
        L->next = q;
    }

    return OK;
}//ListOppose

方法二：

Status ListOppose(LinkList &L)
{   // 将带表头节点的单链表逆置
    LinkList q, p, s;
    p = L->next;
    q = p->next;
    s = q->next;
    p->next = NULL;
    while(s->next)
    {
        q->next = p;
        p = q;
        q = s;
        s = s->next;
    }
    // 将尾结点连接到原表的首元结点
    q->next = p;
    s->next = q;
    L->next = s;
    
    return OK;
}//ListOppose

主函数:

int main()
{
    int i;
    LinkList L;
    InitList(L);
    for(i=1; i<=10; i++)
        CreateList(L, i);
    printf("\n创建的单链表为:\n");
    DispList(L);
    printf("\n逆置后的单链表为:\n");
    ListOppose(L);
    DispList(L);

    return OK;
}

创建好的单链表为：