数据结构与算法里LeetCode 206号链表反转的巧妙解法

反转链表

问题描述

给定单链表的起始节点 head，需将该链表反转并返回反转后的链表头节点。
题目链接

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

核心思想：构建一个新的链表，将原链表的节点依次从头插入到新链表中。

算法步骤

1. 初始化新链表的头节点 newhead 为 NULL。
2. 使用指针 pcur 遍历原链表。
3. 循环过程中：
4. 先保存 pcur 的下一个节点（避免后续节点丢失）。
5. 将 pcur 插入到新链表的头部。
6. 更新新链表的头节点为当前的 pcur。
7. 将 pcur 移动到下一个节点。
8. 当 pcur 为 NULL 时，返回新链表的头节点。
   图示：
   

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead, *pcur;
    newhead = NULL;

    pcur = head;
    while (pcur) {
        struct ListNode* tmp = pcur->next; // 保存当前节点的下一个节点，防止丢失
        // 头插操作
        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 为空：
4. 将 n2 的 next 指针指向 n1（实现当前节点的反转）。
5. 将 n1 移动到 n2 的位置。
6. 将 n2 移动到 n3 的位置。
7. 若 n3 非空，则将 n3 移动到下一个节点。
8. 返回 n1（即新链表的头节点）。
   图示：
   

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    if (n2) // 检查链表是否为空
        n3 = n2->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) // 检查n3是否为空，避免空指针
            n3 = n3->next;
    }
    return n1;
}

注意事项

1. 边界条件处理：
2. 空链表：直接返回 NULL。
3. 单节点链表：无需反转，直接返回头节点。
4. 指针移动顺序：
5. 需先更新 n1 和 n2，再更新 n3。
6. 更新 n3 前需检查其是否为空，防止出现空指针异常。

复杂度分析

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

方法对比分析

总结

反转链表是链表操作中的经典问题，两种方法各有特色：
1. 头插法：思路直观，便于初学者理解链表反转的基本原理。
2. 三指针法：空间效率最优，适用于实际开发中内存敏感的场景。