Merge linked list in-place

[pawan9489]

I was working on a leetcode problem, where I need to merge the elements in the list

input: [0,3,1,0,4,5,2,0]

output: [4,11]

I am able to submit the code by creating a new Linkedlist by reading the input, but couldn't come up with in place solution in Rust. Below is my attempt, where did I go wrong?

// 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
    }
  }
}
struct Solution;
impl Solution {
    pub fn merge_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if head.is_none() {return None}
        type Bl = Box<ListNode>;
        let mut dummy: Bl = Box::new(ListNode::new(0));
        // Assuming first element is 0 & non-empty list
        let mut src_tail: &mut Bl = &mut head.unwrap();
        let mut res_tail: &mut Bl = &mut dummy;
        
        let mut sum = 0;
        // LOOPING src list till end
        while let Some(ref mut node) = src_tail.next {
            sum += node.val;
            
            // if zero then append the accumulated sum to res_tail
            if node.val == 0 {
                res_tail.next = Some(Box::new(ListNode::new(sum)));
                sum = 0;
                if let Some(ref mut post) = res_tail.next {
                    res_tail = post;
                }
            }
            src_tail = node;
        }
        dummy.next
    }

    pub fn merge_nodes_in_place(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        type List = Box<ListNode>;
        if head.is_none() {return None}
        let res = head.clone();
        let mut start: List = head.unwrap();
        while let Some(node) = start.next {
            let mut sum = 0;
            let mut end: List = node;
            while end.val != 0 {
                sum += end.val;
                let tail = end.next.take();
                match tail {
                    Some(next_node) => {
                        end = next_node.next.unwrap();
                    },
                    None => ()
                }
            }
            // end is pointing to 0th Node or next item is None
            end.val = sum;
            if end.next.is_none() {break;}
            start = end.next.unwrap();
        }
        res
    }
}
fn main() {
    let a = Some(Box::new(ListNode { val: 0, next: None }));
    let a = Some(Box::new(ListNode { val: 2, next: a }));
    let a = Some(Box::new(ListNode { val: 5, next: a }));
    let a = Some(Box::new(ListNode { val: 4, next: a }));
    let a = Some(Box::new(ListNode { val: 0, next: a }));
    let a = Some(Box::new(ListNode { val: 1, next: a }));
    let a = Some(Box::new(ListNode { val: 3, next: a }));
    let head = Some(Box::new(ListNode { val: 0, next: a }));

    println!("{:?}", Solution::merge_nodes(head)); 
    // Some(ListNode { val: 4, next: Some(ListNode { val: 11, next: None }) })


    let a = Some(Box::new(ListNode { val: 0, next: None }));
    let a = Some(Box::new(ListNode { val: 2, next: a }));
    let a = Some(Box::new(ListNode { val: 5, next: a }));
    let a = Some(Box::new(ListNode { val: 4, next: a }));
    let a = Some(Box::new(ListNode { val: 0, next: a }));
    let a = Some(Box::new(ListNode { val: 1, next: a }));
    let a = Some(Box::new(ListNode { val: 3, next: a }));
    let head = Some(Box::new(ListNode { val: 0, next: a }));
    println!("{:?}", Solution::merge_nodes_in_place(head)); 
}

[2e71828]

The proximate cause is here:

@pawan9489

        let res = head.clone();

Because Box is an owning pointer, cloning the box also clones its contents. So, you're making a copy of the list, doing things with the original, and then returning the unmodified copy.

[2e71828]

I tried to fix up your solution by adding a bunch of &muts, but I had trouble satisfying the borrow checker. Ultimately, I landed on this, which is more of a departure from your original than I had hoped:

    fn step(cursor: &mut ListNode)->Option<&mut ListNode> {
        let next = cursor.next.as_mut()?;
        return if next.next.is_none() || next.val != 0 {
            cursor.val += next.val;
            let nextnext = next.next.take();
            cursor.next = nextnext;
            Some(cursor)
        } else {
            cursor.next.as_mut().map(|b| &mut **b)
        }
    }

    pub fn merge_nodes_in_place(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut cursor: Option<&mut ListNode> = head.as_mut().map(|b| &mut **b);
        while let Some(node) = cursor {
            cursor = Solution::step(node);
        }
        head
    }

Rust Playground