Question

How to reverse a singly linked list in-place in Rust

Answer 1

// A singly linked list node.
// Each node owns the next node through Box<T>.

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

// Reverse the linked list in-place.
// This consumes the head and returns the new head.
fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev: Option<Box<ListNode>> = None;
    let mut current = head;

    while let Some(mut node) = current {
        // Take ownership of node.next
        let next = node.next.take();

        // Reverse the pointer
        node.next = prev;

        // Move prev and current forward
        prev = Some(node);
        current = next;
    }

    prev
}

// Print the linked list
fn print_list(head: &Option<Box<ListNode>>) {
    let mut temp = head.as_ref();

    while let Some(node) = temp {
        print!("{}", node.value);
        if node.next.is_some() {
            print!(" -> ");
        }
        temp = node.next.as_ref();
    }

    println!();
}

fn main() {
    // Build list: 1 -> 2 -> 3 -> 4 -> 5
    let mut head = Some(Box::new(ListNode {
        value: 1,
        next: Some(Box::new(ListNode {
            value: 2,
            next: Some(Box::new(ListNode {
                value: 3,
                next: Some(Box::new(ListNode {
                    value: 4,
                    next: Some(Box::new(ListNode {
                        value: 5,
                        next: None,
                    })),
                })),
            })),
        })),
    }));

    println!("Original list:");
    print_list(&head);

    // Reverse the list
    head = reverse_list(head);

    println!("Reversed list:");
    print_list(&head);
}


/*
run:

Original list:
1 -> 2 -> 3 -> 4 -> 5
Reversed list:
5 -> 4 -> 3 -> 2 -> 1

*//

 

70+ SQL courses for beginners and professionals