单向链表反转函数（单链表反转问题）



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

示例 1：

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

示例 2：

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

示例 3：输入：head = [] 输出：[]

提示：

• 链表中节点的数目范围是 

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

反转单链表是一道经典的链表操作题目。可以使用两种主要的方法来实现：迭代和递归。

1. 迭代方法思路

• 使用三个指针来反转链表：（前一个节点），（当前节点），和 （下一个节点）。
• 遍历链表，将当前节点的 指针指向前一个节点，更新 和 指针，直到遍历完成。

2. 递归方法思路

• 递归处理链表的尾部，并将每个节点的 指针指向当前节点，从而实现反转。
• 基本的递归策略是：反转链表的其余部分，然后将当前节点追加到反转链表的尾部。

1. 迭代方法复杂度

• 时间复杂度： O(n)O(n)O(n)，其中 nnn 是链表的节点数，每个节点仅遍历一次。
• 空间复杂度： O(1)O(1)O(1)，仅使用常量级别的额外空间。

2. 递归方法思路复杂度

• 时间复杂度： O(n)O(n)O(n)，其中 nnn 是链表的节点数，每个节点仅处理一次。
• 空间复杂度： O(n)O(n)O(n)，递归调用栈的空间复杂度为 O(n)O(n)O(n)。

具体可参考：https://zyfcodes.blog.csdn.net/article/details/

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/haskellbc/25304.html