LeetCode Entry

206. Reverse Linked List

21.03.2024 easy 2024 kotlin rust

Reverse a Linked List

206. Reverse Linked List easy blog post substack youtube

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 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
  }

Bonus: just a single pointer solution

  fun reverseList(head: ListNode?): ListNode? {
    var prev = head
    while (head?.next != null) {
      val next = head?.next?.next
      head?.next?.next = prev
      prev = head?.next
      head?.next = next
    }
    return prev
  }