LeetCode206:反转链表

  • A+
所属分类:算法与数据结构

题目表述

反转一个单链表。

解决方法

迭代反转

思路:依次将原链表的node拆下来,用头插法放在新链表的head上,先拆的就会在新链表的尾部,实现了反转。需要使用三个指针,一个指向curr,一个指向原链表next,一个指向新链表的prev。返回的时候注意,循环结束的条件是curr==null,因此返回的应是prev。

Java代码:

Python3代码

时间复杂度O(n),空间复杂度O(1)

递归反转

思路:参见官方题解

LeetCode206:反转链表

Java代码

时间复杂度O(n),空间复杂度O(1)

运行结果

LeetCode206:反转链表

效率:Java递归>Java迭代>python迭代

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: