C语言实现单链表逆转算法 - 代码详解与示例

使用C语言完成单链表逆转 - 代码详解与示例

本文将展示使用C语言实现单链表逆转的代码，并附带详细的代码注释和运行结果。

代码实现

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

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

ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *curr = head, *next;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

void printList(ListNode* head) {
    ListNode* p = head;
    while (p != NULL) {
        printf('%d ', p->val);
        p = p->next;
    }
    printf('\n');
}

int main() {
    int n, val;
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    ListNode *p = head;
    printf('请输入单链表的长度：');
    scanf('%d', &n);
    printf('请输入单链表的元素：');
    for (int i = 0; i < n; i++) {
        scanf('%d', &val);
        p->val = val;
        if (i == n-1) {
            p->next = NULL;
        } else {
            p->next = (ListNode*)malloc(sizeof(ListNode));
            p = p->next;
        }
    }
    printf('原始单链表：');
    printList(head);
    head = reverseList(head);
    printf('逆转后的单链表：');
    printList(head);
    return 0;
}

代码解析

1. 定义单链表节点结构体

   ListNode 结构体包含两个成员变量：

   • val: 节点的值
   • next: 指向下一个节点的指针

2. 逆转单链表函数 reverseList

   • 使用三个指针 prev, curr, next，分别指向当前节点的前一个节点、当前节点和下一个节点。
   • 循环遍历链表，将当前节点的 next 指针指向其前一个节点，并将 prev 指针更新为当前节点，最后将 curr 指针更新为下一个节点。
   • 循环结束后，prev 指针指向逆转后的链表的头节点，返回 prev。

3. 打印单链表函数 printList

   • 使用一个指针 p 从头节点开始遍历链表，依次打印每个节点的值。

4. 主函数 main

   • 首先创建头节点，并读取用户输入的链表长度和元素值。
   • 使用循环创建链表节点，并设置节点的值和下一个节点指针。
   • 调用 printList 函数打印原始链表。
   • 调用 reverseList 函数逆转链表。
   • 调用 printList 函数打印逆转后的链表。

运行结果

请输入单链表的长度：5
请输入单链表的元素：1 2 3 4 5
原始单链表：1 2 3 4 5 
逆转后的单链表：5 4 3 2 1 

总结

本文详细介绍了使用C语言实现单链表逆转算法的代码，并附带完整的示例代码和运行结果。通过阅读本文，您应该能够理解单链表逆转的原理和实现步骤。

希望本文对您有所帮助！如果您有任何问题，请随时提出。