369. Plus One Linked List
Given a non-negative integer represented as a linked list of digits, plus one to the integer.
The digits are stored such that the most significant digit is at the head
of the list.
Example 1:
Input: head = [1,2,3] Output: [1,2,4]
Example 2:
Input: head = [0] Output: [1]
Constraints:
- The number of nodes in the linked list is in the range
[1, 100]
. 0 <= Node.val <= 9
- The number represented by the linked list does not contain leading zeros except for the zero itself.
Rust Solution
struct Solution;
use rustgym_util::*;
trait Plus {
fn plus(self) -> (ListLink, i32);
}
impl Plus for ListLink {
fn plus(self) -> (ListLink, i32) {
if let Some(mut node) = self {
let val = node.val;
let next = node.next.take();
if next.is_some() {
let (tail, carry) = next.plus();
node.next = tail;
node.val = (val + carry) % 10;
let carry = (val + carry) / 10;
(Some(node), carry)
} else {
node.val = (val + 1) % 10;
let carry = (val + 1) / 10;
(Some(node), carry)
}
} else {
(None, 0)
}
}
}
impl Solution {
fn plus_one(head: ListLink) -> ListLink {
let (tail, carry) = head.plus();
if carry == 1 {
ListLink::link(1, tail)
} else {
tail
}
}
}
#[test]
fn test() {
let head = list!(1, 2, 3);
let res = list!(1, 2, 4);
assert_eq!(Solution::plus_one(head), res);
}
Having problems with this solution? Click here to submit an issue on github.