How to create list?

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.

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

2 Likes

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.

1 Like

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.

2 Likes

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;
    }
}

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.