How to create list?

[kingluo]

I try to write codes for a leetcode problem:

You are given two non-empty linked lists representing two non-negative
integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

The solution is easy, but I encounter such issue: how to create the return list?

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

pub fn add_two_numbers(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut l1_m = l1;
    let mut l2_m = l2;
    let mut num: i32 = 0;

    loop {
        let mut c = 0;

        if let Some(node) = l1_m {
            c += 1;
            num += node.val;
            l1_m = node.next;
        };

        if let Some(node) = l2_m {
            c += 1;
            num += node.val;
            l2_m = node.next;
        };

        if c == 0 {
            break;
        }
    }

    loop {
        let tmp: i32 = num / 10;
        let a: i32 = num - tmp * 10;

        println!("{}", a);
        if tmp == 0 {
            break;
        }
        num = tmp;
    }

    // how to create return list here???
}

fn main() {
    let mut tmp1 = Box::new(ListNode::new(4));
    let tmp2 = Box::new(ListNode::new(4));
    tmp1.next = Some(tmp2);
    let a: Option<Box<ListNode>> = Some(tmp1);
    let b: Option<Box<ListNode>> = Some(Box::new(ListNode::new(9)));
    add_two_numbers(a, b);
}

The ownership of rust seems to be difficult to create common structure in other languages,. Could anybody help? Thanks.

[fernandogmo]

You might find Learn Rust With Entirely Too Many Linked Lists to be a good and thorough reference for linked lists in Rust.

[kornel]

In practice, redesign your algorithm to use Vec, VecDeque, HashMap. They work better with ownership rules, and are likely to be faster (linked lists are a terrible idea on modern CPUs where cache locality and autovectorization matters). For an expression evaluator, you could also use a tree structure, which is also suitable for borrow checking.

[peerreynders]

The first Bad Stack implementation should be perfectly sufficient for the purpose of the exercise.

You'll probably want to add a reverse method to the implementation.

[kingluo]

I use vector to reverse the list, and it works.
But I still think it's a workaround.

pub struct ListNode {
    pub val: i64,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i64) -> Self {
        ListNode { next: None, val }
    }
}

pub struct List {
    head: Option<Box<ListNode>>,
}

impl List {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: i64) {
        let new_node = Box::new(ListNode {
            val: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<i64> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.val
        })
    }
}

pub fn add_two_numbers(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut l1_m = l1;
    let mut l2_m = l2;
    let mut res = List::new();

    let mut fac: i64 = 1;
    let mut num: i64 = 0;
    loop {
        let mut c = 0;

        if let Some(node) = l1_m {
            c += 1;
            //println!("first {}", node.val);
            num += node.val * fac;
            l1_m = node.next;
        };

        if let Some(node) = l2_m {
            c += 1;
            //println!("second {}", node.val);
            num += node.val * fac;
            l2_m = node.next;
        };

        fac *= 10;

        if c == 0 {
            break;
        }
    }

    let mut vec = Vec::new();
    loop {
        let tmp: i64 = num / 10;
        let a: i64 = num - tmp * 10;

        println!("* {}", a);
        vec.push(a);
        if tmp == 0 {
            break;
        }
        num = tmp;
    }

    for i in vec.iter().rev() {
        println!("{}", i);
        res.push(*i);
    }

    println!("len={}", vec.len());
    res.head
}

fn main() {
    let mut list1 = List::new();
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(9);
    list1.push(1);

    let mut list2 = List::new();
    list2.push(9);

    let mut res = add_two_numbers(list1.head, list2.head);
    let mut r = res;
    loop {
        if r.is_none() {
            break;
        }
        let rr = r.unwrap();
        println!("final {}", rr.val);
        r = rr.next;
    }
}

[peerreynders]

I use vector to reverse the list, and it works.

The idiomatic way to reverse a linked list is to pop an element off the source list and to push the element onto the (new) target list - repeatedly until the source list is empty.