「LeetCode每日一题」206. 反转链表
206. 反转链表
题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路
反转链表比较简单，两种方法都说一下。
迭代
迭代就是遍历的时候，直接改变当前节点next的指针指向前一个元素，你需要前存储前一个元素。
时间复杂度：O(n)
空间复杂度：O(1)
递归
递归主要就是为了做反向，代码也比较好写。
时间复杂度：O(n)
空间复杂度：O(n) 这里使用了递归，递归深度可能到n
方案代码
迭代：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, prev = head, None
while cur:
cur.next, prev, cur = prev,cur, cur.next
return prev
递归：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
nextNode = self.reverseList(head.next)
head.next.next = head
head.next = None
return nextNode原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/157.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——169. 多数元素
169. 多数元素 链接：https://leetcode-cn.com/problems/majority-element/难度：简单 题目 给定一个大小为 n 的数组，找到其中…
-
「LeetCode每日一题」—— 22. 括号生成
22. 括号生成 链接：https://leetcode-cn.com/problems/generate-parentheses/难度：中等 题目 数字 n 代表生成括…
-
「LeetCode每日一题」——1071. 字符串的最大公因子
1071. 字符串的最大公因子 链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/难度：…
-
「LeetCode每日一题」——LCCI. 01.06 字符串压缩
LCCI. 01.06 字符串压缩 链接：https://leetcode-cn.com/problems/compress-string-lcci/难度：简单 题目 字符串压缩。…
-
「LeetCode每日一题」—— 200. 岛屿数量
200. 岛屿数量 链接：https://leetcode-cn.com/problems/number-of-islands/难度：中等 思路 这题比较简单，思路就是DFS。 我…
-
「LeetCode每日一题」—— 42. 接雨水
42. 接雨水 链接：https://leetcode-cn.com/problems/trapping-rain-water/难度：困难 题目 给定 n 个非负整数表示…
-
「LeetCode每日一题」—— 33. 搜索旋转排序数组
33. 搜索旋转排序数组 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/难度：中等 题目 点…
-
「LeetCode每日一题」—— 1095. 山脉数组中查找目标值
1095. 山脉数组中查找目标值 链接：https://leetcode-cn.com/problems/find-in-mountain-array/难度：困难 题目 点击原文链…
-
「LeetCode每日一题」—— 912. 排序数组
912. 排序数组 链接：https://leetcode-cn.com/problems/sort-an-array/难度：中等 题目 给你一个整数数组 nums，请你…
-
「LeetCode每日一题」——820. 单词的压缩编码
820. 单词的压缩编码 链接：https://leetcode-cn.com/problems/short-encoding-of-words/难度：中等 题目 给定一个单词列表…
您必须登录才能发表评论。