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.