数据结构与算法：LeetCode 206. 反转链表

反转链表

问题描述

给定单链表的头节点 head，要求反转链表并返回反转后的链表头节点。

思路一：创建新链表头插法

核心思路：创建新链表，将原链表中的节点拿来头插。

算法步骤

1. 初始化新链表头节点 newhead 为 NULL
2. 使用指针 pcur 遍历原链表
3. 每次循环中：
   • 保存 pcur 的下一个节点（防止丢失后续节点）
   • 将 pcur 插入到新链表头部
   • 更新新链表头节点为 pcur
   • 移动 pcur 到下一个节点
4. 当 pcur 为 NULL 时，返回新链表头节点

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* pcur = head;
    while(pcur) {
        struct ListNode* tmp = pcur->next; // 先保存 pcur 的下一个节点
        pcur->next = newhead;              // 头插
        newhead = pcur;
        pcur = tmp;
    }
    return newhead;
}

复杂度分析

• 时间复杂度：O(n)，只需遍历链表一次
• 空间复杂度：O(1)，仅使用固定数量的指针变量

思路二：三指针法

指针定义

• n1：指向已反转部分的最后一个节点（初始为 NULL）
• n2：指向当前待反转节点（初始为头节点）
• n3：指向下一个待反转节点（初始为头节点的下一个节点）

算法步骤

1. 初始化三个指针：n1 = NULL, n2 = head
2. 如果链表非空，则设置 n3 = head->next
3. 循环操作直到 n2 为空：
   • 将 n2 的 next 指针指向 n1（反转当前节点）
   • 将 n1 移动到 位置