【数据结构与算法】206.反转链表(LeetCode)

反转链表

问题描述

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

题目传送门

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

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

算法步骤

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

如图:

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead,*pcur;
    newhead=NULL;
    
    pcur=head;
    while(pcur)
    {
        struct ListNode* tmp=pcur->next;//先保存pcur的下一个节点 头插时会改变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 移动到 n2 位置
   • 将 n2 移动到 n3 位置
   • 如果 n3 不为空，则将 n3 移动到下一个节点
4. 返回 n1（即新链表的头节点）

如图

)

可以看到循环结束的条件是n2为空

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. 边界条件处理：
   • 空链表：直接返回 NULL
   • 单节点链表：无需反转，直接返回头节点
2. 指针移动顺序：
   • 必须先更新 n1 和 n2，再更新 n3
   • 更新 n3 前需要检查其是否为空，避免空指针异常

复杂度分析

• 时间复杂度：O(n)，只需遍历链表一次

• 空间复杂度：O(1)，仅使用固定数量的指针变量

  方法对比分析

总结

反转链表是链表操作中的经典问题，2种方法各有特点：

1. 头插法：直观易懂，适合初学者理解链表反转的基本原理

2. 三指针法：空间效率最优，适合实际开发中的内存敏感场景

受限环境