876.middle-of-the-linked-list.md

問題

https://leetcode.com/problems/middle-of-the-linked-list/

回答

初回の回答: 連結リストを数 n/2+1 だけ head を移動させる。

head の所有権を current に渡してしまうと、head のノード数を出したあとに、真ん中まで移動させることができないので、current には borrow させるようにした。ただ、borrow した値を deref するとき、型に Copy が implement されていないと、所有権の移動が起こってしまう。

以下のエラーメッセージは最後の返り値を *current としたときに出たもの。Copy がない型は clone()するしかない。メモリ余計に使っちゃうけど仕方ない。

cannot move out of `*current` which is behind a shared reference
move occurs because `*current` has type `Option<Box<ListNode>>`, which does not implement the `Copy` trait rustcE0507
main.rs(60, 13): consider borrowing the `Option`'s content: `.as_ref()`

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut current: &Option<Box<ListNode>> = &head;
        let mut n: i32 = 0;
        while let Some(list) = current {
            current = &list.next;
            n += 1;
        }
        if n == 1 {
            return head;
        }

        current = &head;
        for _ in 1..(n / 2) + 1 {
            current = &current.as_ref().unwrap().next
        }
        current.clone()
    }
}

二回目の回答: two runners pointers を使う

一つは一回のループで二回ノードを移動する。もう一つは一回移動する。これによって前者が終端に到達する時点で後者はちょうど真ん中まで移動している状態になる。これは palindrome-linked-list でも使われていたテクニック。

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut fast = head.as_ref();
        let mut slow = head.clone();
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
            slow = slow.unwrap().next;
        }

        slow
    }
}