Блог

Я хочу создать средство проверки палиндромов в Rust, ограничение составляет O (n) времени с 0 (1) дополнительным пространством. Мои идеи:

1. Получить середину связанного списка.
2. Переверните вторую половину связанного списка.
3. Проверьте, идентичны ли первая и вторая половины.

 fn isListPalindrome(l: ListNode<i32>) -> bool {
    let mut fastPointer = amp;l;
    let mut slowPointer = amp;l;
    let mut midIndex = 0;

    // here first step
    loop {
        match fastPointer {
            Some(n) => {
                if let Some(nn) = amp;n.next {
                    fastPointer = amp;nn.next;
                } else {
                    break;
                }
                midIndex  = 1;
            }
            None => break,
        }
        match slowPointer {
            Some(n) => slowPointer = amp;n.next,
            None => break,
        }
    }

    if let Some(_fp) = amp;fastPointer {
        slowPointer = amp;fastPointer;
    }

    // here is second step to reverse list
    let mut prev = None;
    while let Some(n) = slowPointer {
        let next = amp;n.next;
        n.next = prev.take();
        println!("{:?}", n);
        prev = amp;n;
        slowPointer = next;
    }

    true
}
 

Проблема возникла, когда я хочу попробовать отменить вторую половину связанного списка. Ошибка компиляции в коде prev = amp;n;
ошибка :

примечание: ожидаемая ссылка amp;std::option::Option<std::boxed::Box<List<i32>>> найдена ссылка amp;amp;std::boxed::Box<List<i32>>

Как изменить список во второй половине связанного списка для проверки палиндрома выше?

У вас довольно много проблем в вашем коде, не похоже, что у вас есть очень хорошее представление о том, какими типами вы хотите видеть каждую переменную. Когда вы объявляете let mut prev = None; , вы делаете его принадлежащим значению ( Option<T> для некоторых T ), но затем вы присваиваете ему prev = amp;n , что делает его amp;T для некоторых T . Тип принадлежащего значения и заимствованного значения не пересекаются, поэтому эти две строки сами по себе конфликтуют друг с другом. Я создал реализацию обратного алгоритма ниже, и я постарался, чтобы определения типов были как можно более похожи на ваши. Было бы полезно, если бы вы включили их в свой вопрос.

 use std::mem::swap;

#[derive(Debug)]
pub struct List {
    pub val: i32,
    pub next: Option<Box<List>>,
}

type ListNode = Option<Box<List>>;

fn reverse(head: amp;mut ListNode) {
    let tail = amp;mut None;
    while head.is_some() {
        swap(amp;mut head.as_mut().unwrap().next, tail);
        swap(head, tail);
    }
    swap(head, tail);
}

fn main() {
    let mut list = Some(Box::new(List {
        val: 0,
        next: Some(Box::new(List {
            val: 1,
            next: Some(Box::new(List {
                val: 2,
                next: Some(Box::new(List {
                    val: 3,
                    next: None,
                })),
            })),
        })),
    }));
    println!("{:?}", list);
    reverse(amp;mut list);
    println!("{:?}", list);
}
 

Принцип работы алгоритма заключается в том, что на каждой итерации он превращается

head=(H1, H2...), tail=(T...) в

head=(H2...), tail=(H1, T...)

сначала поменяв H2... местами с T... , а затем поменяв head местами и tail . В конечном итоге head это приводит к тому, что он становится пустым и tail содержит обратный список. Затем выполняется одна последняя замена, которая head содержит список.

Если вы хотите отладить свой собственный код, первым шагом будет убедиться, что вы понимаете разницу между T , amp;T , и amp;mut T . T является принадлежащим значением, что означает, что оно будет освобождено в конце его области видимости. amp;T это неизменяемая ссылка на него, которая похожа на указатель в C, за исключением того, что вы не можете изменить значение, на которое он указывает. У вас может быть столько из них, сколько вы хотите, но вы ничего не можете сделать с принадлежащим значением, пока не закончится заимствование. amp;mut T это изменяемое заимствование T , которое снова похоже на указатель, но на этот раз оно позволит вам изменять местоположение, на которое оно указывает. Вы можете иметь один из них одновременно. В контексте связанного списка вам нужно подумать о том, какие типы должна иметь каждая переменная, потому что вы не можете поместить a amp;mut T или a amp;T как next в список, вы можете поместить туда только собственное значение. Вы можете получить принадлежащее значение, используя take() , swap() , и т.д. replace() Возможно, я неправильно понимаю ваш код, и вы можете попробовать что-то другое, но вам почти наверняка не понадобятся какие-либо неизменяемые заимствования ( amp;T ) в вашем обратном алгоритме.