LeetCode Entry

143. Reorder List

23.03.2024 medium 2024 kotlin rust

Reorder Linked List 1->2->3->4->5 -> 1->5->2->4->3

143. Reorder List medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/547

Problem TLDR

Reorder Linked List 1->2->3->4->5 -> 1->5->2->4->3 #medium

Intuition

There are no special hints here. However, the optimal solution will require some tricks:

• use Tortoise And Hare algorithm to find the middle
• reverse the second half
• merge two lists

Approach

• Tortoise And Hare: check fast.next != null to stop right at the middle
• merge lists cleverly: always one into another and swap the points (don’t do this on the interview however, not from the start at least)
• Rust: just gave up and implemented clone()-solution, sorry

Complexity

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

• Space complexity: \(O(1)\), O(n) for my Rust solution. There are O(1) solutions exists on the leetcode.

Code

  fun reorderList(head: ListNode?): Unit {
    var s = head; var f = s
    while (f?.next != null) {
      f = f?.next?.next
      s = s?.next
    }
    f = null
    while (s != null) {
      val next = s.next
      s.next = f
      f = s
      s = next
    }
    s = head
    while (s != null) {
      val next = s.next
      s.next = f
      s = f
      f = next
    }
  }

  pub fn reorder_list(mut head: &mut Option<Box<ListNode>>) {
    let (mut f, mut s, mut c) = (head.clone(), head.clone(), 0);
    while f.is_some() && f.as_mut().unwrap().next.is_some()  {
      f = f.unwrap().next.unwrap().next;
      s = s.unwrap().next; c += 1
    }
    if c < 1 { return }
    let mut prev = None;
    while let Some(mut s_box) = s {
      let next = s_box.next;
      s_box.next = prev;
      prev = Some(s_box);
      s = next;
    }
    let mut s = head;
    while let Some(mut s_box) = s.take() {
      let next = s_box.next;
      if prev.is_none() && !f.is_some() || next.is_none() && f.is_some()  {
        s_box.next = None;
        return;
      }
      s_box.next = prev;
      s = &mut s.insert(s_box).next;
      prev = next;
    }
  }