LeetCode 206 题：反转链表

LeetCode 206 题：反转链表（Reverse Linked List）

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

代码实现

以下是反转单链表的 C 语言实现：

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

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode* next;
};

// 反转链表函数
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;  // 初始化前驱节点为 NULL
    struct ListNode* curr = head; // 当前节点指向链表头部

    while (curr != NULL) {         // 遍历链表直到当前节点为 NULL
        struct ListNode* nextTemp = curr->next; // 暂存当前节点的下一节点
        curr->next = prev;        // 当前节点的指针指向前驱节点
        prev = curr;              // 前驱节点前移
        curr = nextTemp;          // 当前节点后移
    }

    return prev;                  // 返回新链表的头节点
}

测试主函数

以下是用于验证反转链表函数的主函数：

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

// 打印链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->val);
        current = current->next;
    }
    printf("NULL\n");
}

// 测试主函数
int main() {
    // 创建链表：1 -> 2 -> 3 -> 4 -> 5 -> NULL
    struct ListNode* 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);

    // 反转链表
    struct ListNode* reversedHead = reverseList(head);

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

    return 0;
}

逐行讲解代码

1. 链表节点定义

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

• 定义链表的基本节点结构，包括节点的值 val 和指向下一个节点的指针 next。

2. 反转链表函数

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;  // 初始化前驱节点为 NULL
    struct ListNode* curr = head; // 当前节点指向链表头部

• prev 表示前驱节点，初始为空。
• curr 表示当前节点，初始为链表头部。

    while (curr != NULL) {         // 遍历链表直到当前节点为 NULL
        struct ListNode* nextTemp = curr->next; // 暂存当前节点的下一节点
        curr->next = prev;        // 当前节点的指针指向前驱节点
        prev = curr;              // 前驱节点前移
        curr = nextTemp;          // 当前节点后移
    }

• 暂存当前节点的下一节点 nextTemp，以免断链。
• 将当前节点的指针指向前驱节点，实现反转。
• 更新前驱节点和当前节点，准备进入下一步。

    return prev;                  // 返回新链表的头节点
}

• 最后返回 prev，即反转后的链表头节点。

3. 测试链表操作

创建新节点

struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

• 动态分配内存，创建链表节点，并初始化其值。

打印链表

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

• 遍历链表节点并打印其值，直到链表尾部。

测试主函数

int main() {
    // 创建链表：1 -> 2 -> 3 -> 4 -> 5 -> NULL
    struct ListNode* 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);

    // 反转链表
    struct ListNode* reversedHead = reverseList(head);

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

• 打印原链表，调用 reverseList 函数，并打印反转后的链表。

运行结果

运行上述代码，输出结果如下：

原链表: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
反转后的链表: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为链表节点数。每个节点遍历一次。
• 空间复杂度：$O(1)$，仅使用了几个指针变量。