用C语言如何逆置一个单链表

创作时间:

作者:

@小白创作中心

用C语言如何逆置一个单链表

引用

来源

https://docs.pingcode.com/baike/1101123

在数据结构和算法的学习中，单链表的逆置是一个常见的操作。本文将详细介绍如何使用C语言实现单链表的逆置，包括迭代法和递归法两种方法，并对比它们的优缺点。

用C语言逆置一个单链表的方法有：使用迭代法、递归法。这两种方法各有优缺点，适用于不同的场景。下面将详细介绍使用迭代法逆置单链表的步骤和代码实现，并对其进行详细的解释和分析。

一、迭代法逆置单链表

迭代法是一种常用且高效的逆置单链表的方法。其核心思想是通过逐个改变每个节点的指针方向来实现链表的逆置。

1.1 迭代法的基本步骤

初始化三个指针：prev、current 和 next。
遍历链表，将 current 指向 prev。
将 prev 和 current 向前移动一个节点。
重复上述步骤直到 current 变为 NULL。

1.2 迭代法代码实现

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

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

// 逆置单链表函数  
struct Node* reverseList(struct Node* head) {  
    struct Node* prev = NULL;  
    struct Node* current = head;  
    struct Node* next = NULL;  
    while (current != NULL) {  
        // 保存下一个节点  
        next = current->next;  
        // 反转当前节点的指针  
        current->next = prev;  
        // 向前移动指针  
        prev = current;  
        current = next;  
    }  
    return prev;  
}  

// 创建新节点函数  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  

// 打印链表函数  
void printList(struct Node* head) {  
    struct Node* temp = head;  
    while (temp != NULL) {  
        printf("%d -> ", temp->data);  
        temp = temp->next;  
    }  
    printf("NULL\n");  
}  

// 主函数  
int main() {  
    struct Node* head = createNode(1);  
    head->next = createNode(2);  
    head->next->next = createNode(3);  
    head->next->next->next = createNode(4);  
    printf("Original List:\n");  
    printList(head);  
    head = reverseList(head);  
    printf("Reversed List:\n");  
    printList(head);  
    return 0;  
}

二、递归法逆置单链表

递归法是一种更具技巧性的方法，通过递归调用实现链表的逆置。其核心思想是将链表看作头节点与剩余部分的组合，递归逆置剩余部分，然后调整头节点的指针。

2.1 递归法的基本步骤

递归逆置剩余链表。
将当前节点的下一个节点的指针指向当前节点。
将当前节点的指针置为 NULL。

2.2 递归法代码实现

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

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

// 递归逆置单链表函数  
struct Node* reverseListRecursive(struct Node* head) {  
    // 基本情况：空链表或只有一个节点的链表  
    if (head == NULL || head->next == NULL) {  
        return head;  
    }  
    // 递归逆置剩余链表  
    struct Node* rest = reverseListRecursive(head->next);  
    // 调整指针方向  
    head->next->next = head;  
    head->next = NULL;  
    return rest;  
}  

// 创建新节点函数  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  

// 打印链表函数  
void printList(struct Node* head) {  
    struct Node* temp = head;  
    while (temp != NULL) {  
        printf("%d -> ", temp->data);  
        temp = temp->next;  
    }  
    printf("NULL\n");  
}  

// 主函数  
int main() {  
    struct Node* head = createNode(1);  
    head->next = createNode(2);  
    head->next->next = createNode(3);  
    head->next->next->next = createNode(4);  
    printf("Original List:\n");  
    printList(head);  
    head = reverseListRecursive(head);  
    printf("Reversed List:\n");  
    printList(head);  
    return 0;  
}