C中单链表反序的实现方法是什么？

C中单链表反序的实现方法

在C语言中，单链表的反序操作可以通过多种方法实现，主要包括迭代法和递归法。以下是详细的实现步骤和示例代码。

迭代法实现单链表反序

迭代法是通过遍历链表，将当前节点的指针指向前一个节点，从而实现链表的逆序。具体步骤如下：

1. 「定义节点结构体」：定义一个包含数据和指向下一个节点指针的结构体。
2. 「初始化指针」：初始化三个指针，分别指向当前节点、前一个节点和下一个节点。
3. 「遍历链表」：遍历链表，将当前节点的指针指向前一个节点，然后移动指针，直到遍历完成。
4. 「更新头节点」：将头节点指向最后一个节点，即逆序后的链表头节点。

示例代码

#include <stdio.h>

#include <stdlib.h>



// 定义链表节点结构体

typedef struct Node {

    int data;

    struct Node* next;

} Node;



// 创建新节点

Node* createNode(int data) {

    Node*newNode = (Node*)malloc(sizeof(Node));

    if (newNode == NULL) {

        printf("内存分配失败\n");

        return NULL;

    }

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}



// 打印链表

void printList(Node* head) {

    Node* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}



// 反转链表

Node*reverseList(Node* head) {

    Node* prev = NULL;

    Node* current = head;

    Node* next = NULL;

    

    while (current != NULL) {

        next = current->next;  // 保存下一个节点

        current->next = prev;  // 将当前节点的next指向前一个节点

        prev = current;        // 将prev移动到当前节点

        current = next;        // 将current移动到下一个节点

    }

    head = prev;  // 更新头节点为最后一个节点

    return head;

}



int main() {

    Node* head = NULL;

    head = createNode(1);

    head->next = createNode(2);

    head->next->next = createNode(3);

    head->next->next->next = createNode(4);

    head->next->next->next->next = createNode(5);



    printf("原始链表: ");

    printList(head);



    head = reverseList(head);



    printf("反转后的链表: ");

    printList(head);



    return 0;

}

递归法实现单链表反序

递归法是通过递归调用函数来实现链表的逆序。具体步骤如下：

1. 「递归终止条件」：如果当前节点为空或只有一个节点，则直接返回当前节点。
2. 「递归调用」：递归调用函数处理下一个节点。
3. 「调整指针」：将当前节点的下一个节点的next指针指向当前节点，然后将当前节点的next指针置为NULL。
4. 「返回头节点」：返回递归调用的结果，即逆序后的链表头节点。

示例代码

#include <stdio.h>

#include <stdlib.h>



// 定义链表节点结构体

typedef struct Node {

    int data;

    struct Node* next;

} Node;



// 创建新节点

Node* createNode(int data) {

    Node*newNode = (Node*)malloc(sizeof(Node));

    if (newNode == NULL) {

        printf("内存分配失败\n");

        return NULL;

    }

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}



// 打印链表

void printList(Node* head) {

    Node* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}



// 递归反转链表

Node*reverseListRecursive(Node* head) {

    if (head == NULL || head->next == NULL) {

        return head;

    }

    Node* newHead = reverseListRecursive(head->next);

    head->next->next = head;

    head->next = NULL;

    return newHead;

}



int main() {

    Node* head = NULL;

    head = createNode(1);

    head->next = createNode(2);

    head->next->next = createNode(3);

    head->next->next->next = createNode(4);

    head->next->next->next->next = createNode(5);



    printf("原始链表: ");

    printList(head);



    head = reverseListRecursive(head);



    printf("反转后的链表: ");

    printList(head);



    return 0;

}

总结

以上两种方法都可以有效地实现单链表的逆序操作。迭代法通过遍历链表并调整指针指向关系来实现逆序，而递归法则通过递归调用函数来处理每个节点的逆序操作。根据具体需求和场景选择合适的方法即可。