👋

[rust] 2. Add Two Numbers/60 questions to solve

2024/10/06に公開

Leet Codeのおすすめされていた60問を解いた自己学習メモです。
Leet Codeのリスト機能
https://leetcode.com/list/xo2bgr0r

おすすめされていた元記事
https://1kohei1.com/leetcode/

前回の記事
https://zenn.dev/yut_wq/articles/8b7199ad27333b

2. Add Two Numbers

一言まとめ

LinkedListでnodeをたどる際には、nodeの現在位置を控えておく。
LinkedListの先頭にダミーnodeを入れておくと、プログラムが簡易になることがある。
rustのlspでエラーが出る場合、コンパイルを試みることで、詳細なメッセージが確認できる。

解法

公式の解説ではうまくrustで実装できなかったので、以下のサイトで解法を確認し、参考にし実装。
https://medium.com/@AlexanderObregon/solving-the-add-two-numbers-problem-on-leetcode-rust-solutions-walkthrough-b8fd2a1255a1#:~:text=The ‘Add Two Numbers’ problem on

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut l1 = l1;
        let mut l2 = l2;

        let mut carry = 0;
        // full list contain dummy head.
        let mut l3 = Box::new(ListNode::new(0));
        // last node in the list
        let mut current_node = &mut l3;

        loop {
            if l1.is_none() && l2.is_none() && carry == 0 {
                break;
            }

            let x = match l1.as_ref() {
                Some(node) => node.val,
                None => 0,
            };
            let y = match l2.as_ref() {
                Some(node) => node.val,
                None => 0,
            };
            let sum = x + y + carry;
            carry = sum / 10;

            // update `current_node`
            current_node.next = Some(Box::new(ListNode::new(sum % 10)));
            current_node = current_node.next.as_mut().unwrap();

            // update `l1`, `l2`
            l1 = match l1 {
                Some(node) => node.next,
                None => None
            };
            l2 = match l2 {
                Some(node) => node.next,
                None => None
            };
        }
        return l3.next;
    }
}

詰まったところ

l1,l2の更新ができなかった。
→シャドーイングで解決。

ループ毎に新しいnodeを追加する方法がわからなかった。
l3の最後までnodeをたどって、新しいnodeを追加しようとした。
n回目のループではn回のunwrap()を行い、ListNode::new()で要素を追加しようとした。
current_node変数で最終nodeを記録することで解決。

returnl3をそのまま返そうとした。
l3の初期値を l1の最初の要素 + l2の最初の要素 にしたかった。
ループの中でうまいこと初期値を設定する方法がわからなかった。
l3の最初のnodeをダミーnodeにし、l3の2要素目以降を返すことで解決。

参考文献

https://medium.com/@AlexanderObregon/solving-the-add-two-numbers-problem-on-leetcode-rust-solutions-walkthrough-b8fd2a1255a1#:~:text=The ‘Add Two Numbers’ problem on

Discussion