LeetCode Entry

234. Palindrome Linked List

22.03.2024 easy 2024 kotlin rust

Is Linked List a palindrome

234. Palindrome Linked List easy blog post substack youtube

Problem TLDR

Is Linked List a palindrome #easy

Intuition

Find the middle using tortoise and hare algorithm and reverse it simultaneously.

Approach

• the corners case is to detect odd or even count of nodes and do the extra move
• gave up on the Rust solution without clone()

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\), O(n) in Rust

Code

  fun isPalindrome(head: ListNode?): Boolean {
    var fast = head; var slow = head
    var prev: ListNode? = null
    while (fast?.next != null) {
      fast = fast?.next?.next
      val next = slow?.next
      slow?.next = prev
      prev = slow
      slow = next
    }
    if (fast != null) slow = slow?.next
    while (prev != null && prev?.`val` == slow?.`val`)
      prev = prev?.next.also { slow = slow?.next }
    return prev == null
  }

  pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    let (mut fast, mut slow, mut prev) = (head.clone(), head, None);
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        fast = fast.unwrap().next.unwrap().next;
        let mut slow_box = slow.unwrap();
        let next = slow_box.next;
        slow_box.next = prev;
        prev = Some(slow_box);
        slow = next
    }
    if fast.is_some() { slow = slow.unwrap().next }
    while let Some(prev_box) = prev {
      let slow_box = slow.unwrap();
      if prev_box.val != slow_box.val { return false }
      prev = prev_box.next; slow = slow_box.next
    }; true
  }