C语言实现单链表的就地逆置算法

简介

单链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。链表的逆置是指将链表中的元素顺序颠倒。

本文将介绍如何使用C语言实现单链表的就地逆置算法，并提供完整的代码示例。该算法通过头插法将链表元素逐个插入到头结点之后，实现链表的反转。

代码实现

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

// 定义单链表节点
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *Linklist;

// 单链表就地逆置
void reverseLinklist(Linklist L) {
    LNode *p = L->next;
    L->next = NULL;

    while (p != NULL) {
        LNode *r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
}

// 创建单链表
Linklist createLinkedList(int arr[], int n) {
    Linklist L = (Linklist)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *tail = L;

    for (int i = 0; i < n; i++) {
        LNode *newNode = (LNode *)malloc(sizeof(LNode));
        newNode->data = arr[i];
        newNode->next = NULL;

        tail->next = newNode;
        tail = newNode;
    }

    return L;
}

// 打印单链表
void printLinkedList(Linklist L) {
    LNode *current = L->next;

    while (current != NULL) {
        printf('%d ', current->data);
        current = current->next;
    }
    printf('
');
}

// 销毁单链表
void destroyLinkedList(Linklist L) {
    LNode *current = L;
    LNode *next = NULL;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    Linklist L = createLinkedList(arr, n);

    printf('原始链表：');
    printLinkedList(L);

    reverseLinklist(L);

    printf('逆置后链表：');
    printLinkedList(L);

    destroyLinkedList(L);

    return 0;
}

代码说明

reverseLinklist 函数实现了单链表的就地逆置算法。
createLinkedList 函数用于创建一个单链表。
printLinkedList 函数用于打印单链表。
destroyLinkedList 函数用于销毁单链表。

运行结果

原始链表：1 2 3 4 5 
逆置后链表：5 4 3 2 1

总结

本文介绍了如何使用C语言实现单链表的就地逆置算法，并提供了完整的代码示例。该算法简单易懂，效率较高，适用于对单链表进行逆置操作的场景。