C语言单向链表逆转算法详解及代码示例

本文将详细介绍使用C语言建立单向链表并实现节点逆转的算法。包含代码示例、算法步骤和输出结果，帮助您深入理解单向链表逆转的原理和操作方法。

问题描述:

假设有一个包含若干整数的单向链表，例如: 1,2,3,4,51,2,3,4,5。现在需要通过某些算法将其中各个节点逆转，得到新的链表: 5,4,3,2,15,4,3,2,1。

代码示例:

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

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

// 在链表尾部插入节点
void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* curr = *head;
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

// 逆转链表
void reverse(struct Node** head) {
    struct Node *prev, *curr, *next;
    prev = NULL;
    curr = *head;

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

    *head = prev;
}

// 打印链表
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf('%d ', curr->data);
        curr = curr->next;
    }
    printf('
');
}

int main() {
    struct Node* head = NULL;

    // 在链表尾部插入节点
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 51);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 5);

    printf("原始链表: ");
    printList(head);

    // 逆转链表
    reverse(&head);

    printf("逆转后链表: ");
    printList(head);

    return 0;
}

输出结果:

原始链表: 1 2 3 4 51 2 3 4 5 
逆转后链表: 5 4 3 2 51 4 3 2 1

算法步骤:

初始化: 声明三个指针 prev、curr 和 next，分别指向逆转后的前一个节点、当前节点和下一个节点。初始化 prev 为 NULL，curr 为链表头节点。
遍历链表: 循环遍历链表，直到 curr 指针指向 NULL。
修改指针: 在每次循环中，首先将 next 指针指向 curr 的下一个节点。然后将 curr 的 next 指针指向 prev，将当前节点的指向反转。最后更新 prev 指针指向 curr，curr 指针指向 next，准备指向下一个节点。
更新头节点: 循环结束后，prev 指针指向最后一个节点，也就是逆转后的头节点。更新头节点指针 head 指向 prev。

总结:

本文通过代码示例和算法步骤详细解释了使用C语言实现单向链表逆转的算法。希望本文能帮助您更好地理解和运用链表逆转算法。