C语言实现单链表的原地逆置算法（附详细代码讲解）

本文将介绍如何使用C语言实现单链表的原地逆置，并提供详细的代码示例和算法分析，帮助你理解并掌握这一常见的数据结构操作。

1. 单链表逆置问题描述

单链表是一种常见的数据结构，每个节点包含数据和指向下一个节点的指针。单链表的逆置指的是将链表中所有节点的指针反转，使得链表的顺序颠倒。

例如，原始链表为 1 -> 2 -> 3 -> 4 -> 5，逆置后的链表应为 5 -> 4 -> 3 -> 2 -> 1。

2. 原地逆置算法

原地逆置算法是指在不使用额外存储空间的情况下，直接修改链表节点的指针来完成逆置操作。

算法步骤：

定义三个指针：prev、current 和 next。2. 初始化 prev 为 NULL，current 为链表的头节点。3. 遍历链表，进行以下操作： - 将 next 指向 current 的下一个节点。 - 将 current 的 next 指针指向 prev，实现反转。 - 将 prev 移动到 current。 - 将 current 移动到 next。4. 循环结束后，将链表的头节点指向 prev，完成逆置。

3. C语言代码实现c#include <stdio.h>#include <stdlib.h>

// 定义单链表节点的结构体typedef struct Node { int data; struct Node* next;} Node;

// 原地逆置单链表void reverseLinkedList(Node** head) { Node* prev = NULL; Node* current = head; Node next = NULL;

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

*head = prev;}

// 创建单链表Node* createLinkedList(int arr[], int n) { Node* head = NULL; Node* tail = NULL;

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

    if (head == NULL) {            head = newNode;            tail = newNode;        } else {            tail->next = newNode;            tail = newNode;        }    }

return head;}

// 打印单链表void printLinkedList(Node* head) { Node* current = head;

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

');}

// 销毁单链表void destroyLinkedList(Node* head) { Node* current = head; Node* 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]);

Node* head = createLinkedList(arr, n);

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

reverseLinkedList(&head);

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

destroyLinkedList(head);

return 0;}

4. 代码讲解

reverseLinkedList 函数实现了单链表的原地逆置算法，具体步骤如上述算法描述。- createLinkedList 函数用于创建一个单链表，接收一个数组和数组长度作为参数，返回链表的头节点。- printLinkedList 函数用于打印单链表的所有节点值。- destroyLinkedList 函数用于释放单链表占用的内存空间。

5. 总结

本文详细介绍了使用C语言实现单链表原地逆置的算法和代码示例，并对代码进行了详细的讲解。希望本文能够帮助你理解并掌握这一常见的数据结构操作。