在 Rust 中就地合并链表

Question

我正在研究一个 leetcode problem，我需要在其中合并列表中的元素

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

output: [4,11]

我已经通过创建一个新的 Linkedlist 提交了代码，但是无法在 Rust 中找到合适的解决方案。我哪里错了？

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

Answer 1

impl Solution {
    fn consume_next_node(cursor: &mut ListNode)->Option<&mut ListNode> {
        let next = cursor.next.as_mut()?;
        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::consume_next_node(node);
        }
        head
    }
}

在 Rust 中就地合并链表

Merge linked list in-place in Rust

algorithm

linked-list

rust