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

问题描述

给定一个存储整数的单链表，要求在不使用额外存储空间的情况下，将链表原地逆置。

例如，对于链表 1->2->3->4->NULL，逆置后的链表应为 4->3->2->1->NULL。

算法思路

该算法使用三个指针：prev、current 和 next，分别指向当前节点的前一个节点、当前节点和下一个节点。算法步骤如下：

1. 初始化 prev 为 NULL，current 为头结点的下一个节点，next 为 NULL。
2. 遍历链表，每次迭代执行以下操作：
   • 将 next 指向 current 的下一个节点。
   • 将 current 的 next 指针指向 prev，实现反转。
   • 将 prev 移动到 current，current 移动到 next。
3. 循环结束后，prev 指向最后一个节点，将其设置为头结点的下一个节点即可完成逆置。

代码实现

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

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

ListNode* createListNode(int data) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    node->next = NULL;
    return node;
}

ListNode* createLinkedList(int* arr, int n) {
    if (n <= 0) {
        return NULL;
    }
    
    ListNode* head = createListNode(0); // 头结点
    ListNode* tail = head;
    
    for (int i = 0; i < n; i++) {
        ListNode* newNode = createListNode(arr[i]);
        tail->next = newNode;
        tail = newNode;
    }
    
    return head;
}

void printLinkedList(ListNode* head) {
    ListNode* current = head->next;
    
    while (current != NULL) {
        printf('%d ', current->data);
        current = current->next;
    }
    
    printf('\n');
}

void reverseLinkedList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head->next;
    ListNode* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    head->next = prev;
}

int main() {
    int n;
    scanf('%d', &n);
    
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf('%d', &arr[i]);
    }
    
    ListNode* head = createLinkedList(arr, n);
    
    reverseLinkedList(head);
    
    printLinkedList(head);
    
    return 0;
}

示例输入输出

输入：

5
1 2 3 4 5

输出：

5 4 3 2 1

总结

本文介绍了如何使用 C 语言实现单链表的就地逆置算法，并提供了详细的代码示例和算法解析。该算法通过巧妙地操作指针，在不使用额外存储空间的情况下实现了链表的逆置，体现了算法设计的精妙之处。