双鸭山市网站建设_网站建设公司_服务器部署_seo优化

题目描述

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

示例 1：

输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]输出：[2,1]

示例 3：

输入：head = []输出：[]

提示：

• 链表中节点的数目范围是[0, 5000]
• -5000 <= Node.val <= 5000

解决方案：

这段代码的核心功能是反转一个单链表（将链表的节点指向全部倒置，比如原链表 1→2→3→null 变为 3→2→1→null），采用「迭代法」实现，时间复杂度为O(n)（n为链表节点数），空间复杂度为O(1)（仅使用常量级额外空间），是反转单链表的经典高效解法。

核心逻辑

代码通过维护三个指针（pre、cur、nxt），逐个改变节点的指向，全程只需一次遍历：

1. 指针初始化：pre为nullptr（表示当前节点的前一个节点，初始无），cur指向链表头节点（待处理的当前节点），nxt暂存当前节点的下一个节点；
2. 迭代反转：循环处理每个节点，直到cur为nullptr（遍历完所有节点）：
   • 先用nxt保存cur->next（防止反转指向后丢失后续节点）；
   • 将cur->next指向pre（完成当前节点的反转）；
   • pre移动到cur（成为下一个节点的 “前节点”）；
   • cur移动到nxt（处理下一个节点）；
3. 返回结果：循环结束时，pre指向原链表的最后一个节点（即反转后链表的头节点），返回pre即可。

总结

1. 核心思路：通过三个指针 “接力”，逐个反转节点指向，避免递归带来的额外空间开销；
2. 关键操作：每次反转前用nxt保存后续节点，是防止链表断裂的核心；
3. 效率特点：一次遍历完成反转，时间O(n)、空间O(1)，是反转单链表的最优解法之一。

函数源码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre=nullptr; ListNode* cur=head; ListNode* nxt=nullptr; while(cur){ nxt=cur->next; cur->next=pre; pre=cur; cur=nxt; } return pre; } };