欢迎光临散文网 会员登陆 & 注册

AcWing 35. 反转链表

2023-03-05 17:39 作者:1234DW  | 我要投稿


(链表操作,迭代) O(n)

翻转即将所有节点的next指针指向前驱节点。

由于是单链表,我们在迭代时不能直接找到前驱节点,所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前,不要忘记保存它的后继节点。

空间复杂度分析:遍历时只有3个额外变量,所以额外的空间复杂度是 O(1)

时间复杂度分析:只遍历一次链表,时间复杂度是 O(n)



AcWing 35. 反转链表的评论 (共 条)

分享到微博请遵守国家法律