👋
[rust] 2. Add Two Numbers/60 questions to solve
Leet Codeのおすすめされていた60問を解いた自己学習メモです。
Leet Codeのリスト機能
おすすめされていた元記事
前回の記事
2. Add Two Numbers
一言まとめ
LinkedListでnodeをたどる際には、nodeの現在位置を控えておく。
LinkedListの先頭にダミーnodeを入れておくと、プログラムが簡易になることがある。
rustのlspでエラーが出る場合、コンパイルを試みることで、詳細なメッセージが確認できる。
解法
公式の解説ではうまくrustで実装できなかったので、以下のサイトで解法を確認し、参考にし実装。
// 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を記録することで解決。
return
でl3
をそのまま返そうとした。
l3
の初期値を l1
の最初の要素 + l2
の最初の要素 にしたかった。
ループの中でうまいこと初期値を設定する方法がわからなかった。
→l3
の最初のnodeをダミーnodeにし、l3
の2要素目以降を返すことで解決。
参考文献
Discussion