21.03.2024
206. Reverse Linked List easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/545
Problem TLDR
Reverse a Linked List #easy
Intuition
We need at least two pointers to store the current node and previous.
Approach
In a recursive approach:
treat result as a new head
erase the link to the next
next.next must point to the current
Complexity
Time complexity:
O(n)Space complexity:
O(1) or log(n) for the recursion
Code
fun reverseList(head: ListNode?): ListNode? =
head?.next?.let { next ->
head.next = null
reverseList(next).also { next?.next = head }
} ?: head
pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut curr = head; let mut prev = None;
while let Some(mut curr_box) = curr {
let next = curr_box.next;
curr_box.next = prev;
prev = Some(curr_box);
curr = next;
}
prev
}