055. 实现链表的反转

在C语言中，链表的反转是一个常见的操作，它可以通过迭代或递归的方式实现。链表反转的核心思想是改变链表中每个节点的指针方向，使其指向前一个节点。

1. 迭代法实现链表反转

迭代法通过三个指针（prev、current 和 next）逐步反转链表。

#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");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 迭代法反转链表
void reverseLinkedListIterative(Node** head) {
    Node* prev = NULL;
    Node* current = *head;
    Node* next = NULL;

    while (current != NULL) {
        next = current->next;  // 保存下一个节点
        current->next = prev;  // 反转当前节点的指针
        prev = current;        // 移动 prev 和 current
        current = next;
    }
    *head = prev; // 更新头指针
}

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

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表：\n");
    printLinkedList(head);

    reverseLinkedListIterative(&head);

    printf("反转后的链表：\n");
    printLinkedList(head);

    return 0;
}

2. 递归法实现链表反转

递归法通过递归调用逐步反转链表。

#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");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 递归法反转链表
Node* reverseLinkedListRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head; // 递归终止条件
    }

    Node* newHead = reverseLinkedListRecursive(head->next); // 递归反转剩余部分
    head->next->next = head; // 反转当前节点的指针
    head->next = NULL;       // 当前节点成为新的尾节点
    return newHead;          // 返回新的头指针
}

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

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表：\n");
    printLinkedList(head);

    head = reverseLinkedListRecursive(head);

    printf("反转后的链表：\n");
    printLinkedList(head);

    return 0;
}

代码说明

迭代法

1. 使用三个指针 prev、current 和 next。
2. 遍历链表，逐步反转每个节点的指针。
3. 最后更新头指针。

递归法

1. 递归终止条件：如果链表为空或只有一个节点，直接返回。
2. 递归反转剩余部分。
3. 反转当前节点的指针。
4. 返回新的头指针。

示例运行

输入：

无输入

输出：

原始链表：
1 -> 2 -> 3 -> 4 -> NULL
反转后的链表：
4 -> 3 -> 2 -> 1 -> NULL

链表反转的特点

效率：

• 迭代法和递归法的时间复杂度均为 O(n)，其中 n 是链表的长度。

• 迭代法的空间复杂度为 O(1)，而递归法的空间复杂度为 O(n)，因为递归调用会占用栈空间。

适用性：

• 迭代法更适合实际应用，因为它不需要额外的栈空间。

• 递归法代码更简洁，但需要注意递归深度，避免栈溢出。

通过使用迭代法或递归法，可以高效地实现链表的反转。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)