数据结构——链表逆序详解

一、示例

二、上代码

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

// 定义节点结构体
struct Node {
    int val;
    struct Node* next;
};

// 定义链表结构体
struct LinkedList {
    struct Node* head;
    struct Node* tail;
    int length;
};

// 递归法翻转链表
struct Node* reverseLinkedList(struct Node* head) {
    // 如果链表为空或只有一个节点，直接返回该节点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 递归翻转链表的其余部分
    struct Node* newHead = reverseLinkedList(head->next);

    // 翻转当前节点的指针
    head->next->next = head;
    head->next = NULL;

    // 返回新的头节点
    return newHead;
}

// 辅助函数，用于设置链表的头节点
void setHead(struct LinkedList* list, struct Node* head) {
    list->head = head;
}

int main() {
    struct LinkedList list;
    list.head = NULL;
    list.tail = NULL;
    list.length = 0;

    // 创建链表
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node5 = (struct Node*)malloc(sizeof(struct Node));

    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    node5->val = 5;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;

    list.head = node1;

    // 翻转链表
    struct Node* reversedList = reverseLinkedList(list.head);

    // 输出翻转后的链表
    struct Node* current = reversedList;
    while (current) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");

    return 0;
}

三、详解

以上使用了递归的方法来实现链表的反转，下面是这个递归函数的详细分析：

基本情况：

如果 head 是 null 或者 head.next 是 null，这意味着链表为空或者只有一个节点。在这种情况下，函数直接返回 head，因为不需要进行反转。

递归调用：

如果链表有两个或更多的节点，函数会调用自身来反转从 head.next 开始的子链表。这会得到一个新的头节点 newHead，它是原始链表中除了第一个节点之外的所有节点的反转链表的头节点。
反转当前节点：

在递归调用返回后，head 指向原始链表的第一个节点，而 newHead 指向反转后的子链表的头节点。
head.next.next = head 这行代码将 head 节点的下一个节点的 next 指针指向 head 本身，这实际上是将 head 节点插入到反转后的子链表的头部。
head.next = null 这行代码将 head 节点的 next 指针设置为 null，以完成反转操作。

返回新的头节点：

最后，函数返回 newHead，这是反转后的链表的新头节点。

动态调用过程示例：

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> 5

第一次调用：head 是 1。
因为 head.next 不是 null，所以调用 reverseLinkedList(head.next)，即 reverseLinkedList(2)。

第二次调用：head 是 2。
因为 head.next 不是 null，所以调用 reverseLinkedList(head.next)，即 reverseLinkedList(3)。

第三次调用： head 是 3。
因为 head.next 不是 null，所以调用 reverseLinkedList(head.next)，即 reverseLinkedList(4)。

第四次调用：head 是 4。
因为 head.next 不是 null，所以调用 reverseLinkedList(head.next)，即 reverseLinkedList(5)。

第五次调用：head 是 5。
因为 head.next 是 null，所以直接返回 head，即 5。

第四次调用返回：newHead 是 5。head 是 4。
head.next.next = head 将 5 的 next 指针指向 4。
head.next = null 将 4 的 next 指针设置为 null。
返回 newHead，即 5。

第三次调用返回：newHead 是 5。head 是 3。
head.next.next = head 将 4 的 next 指针指向 3。
head.next = null 将 3 的 next 指针设置为 null。
返回 newHead，即 5。

第二次调用返回：newHead 是 5。head 是 2。
head.next.next = head 将 3 的 next 指针指向 2。
head.next = null 将 2 的 next 指针设置为 null。
返回 newHead，即 5。

第一次调用返回：newHead 是 5。head 是 1。
head.next.next = head 将 2 的 next 指针指向 1。
head.next = null 将 1 的 next 指针设置为 null。
返回 newHead，即 5。

最终，函数返回 newHead，即反转后的链表的头节点 5，链表变为 5 -> 4 -> 3 -> 2 -> 1。

原文地址：https://blog.csdn.net/vavid317/article/details/143801381

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！