LeetCode Entry

876. Middle of the Linked List

07.03.2024 easy 2024 kotlin rust

Middle of the Linked List

876. Middle of the Linked List easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/531

Problem TLDR

Middle of the Linked List #easy

Intuition

Use Tortoise and Hare algorithm https://cp-algorithms.com/others/tortoise_and_hare.html

Approach

We can check fast.next or just fast, but careful with moving slow. Better test yourself with examples: [1], [1,2], [1,2,3], [1,2,3,4].

Complexity

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

  • Space complexity: \(O(1)\)

Code


  fun middleNode(head: ListNode?): ListNode? {
    var s = head; var f = s
    while (f?.next != null) {
      f = f?.next?.next; s = s?.next
    }
    return s
  }



    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
      let (mut s, mut f) = (head.clone(), head);
      while f.is_some() {
        f = f.unwrap().next;
        if f.is_some() { f = f.unwrap().next; s = s.unwrap().next }
      }
      s
    }