Рекурсивные Обратный Список

Question

Мне нужно написать алгоритм, называемый reverseNodes, который принимает RefToNode в качестве параметра и recuriveley переворачивает список заголовка я придумал был

Алгоритм обратного (Rlist)

reverves elementsin списка

Pre: Rlist :: Referance в список, чтобы быть отменен

сообщение: элементы Rlist перепутаны

, если (Rlist! = NULL) reverseNodes (Rlist -> голова) возвращение

мне нужно найти способ, чтобы написать это psuedocode и найти временную сложность

Answer 1

Иногда проще создать несколько ип -формальный алгоритм тарабарщины, если вы начинаете с четко выраженной идеей. Затем, запутавшись и вербализации, пока у вас не появится что-то, ваш профессор с радостью примет.

Итак, давайте начнем с нашей общей идеей алгоритма:

let rec fold folder acc l = 
    match l with 
    | [] -> acc 
    | x::xs -> fold folder (folder acc x) xs 

let prepend l e = e :: l 

let revlist l = fold prepend [] l 

... и начать разглагольствовать:

1. Пусть результат = пустой список
2. Пусть L = список мы хотим обратить вспять
3. если l - пустой список, goto 7
4. let head = l.front, l = l.pop_front()
5. result.push_front голова
6. Гото 3
7. л = результат

Шаги 3..6 легко могут быть выражены в виде рекурсивной функции:

void loop(list& l, list& result) 
{ 
    if(l.is_empty()) return; 
    auto head = l.front(); 
    l.pop_front(); 
    result.push_front(head); 
    loop(l,result); 
} 

Поскольку мы хотим создать иллюзию in-place.reversal, наша функция reverse_list -

void reverse_list(list& l) 
{ 
    list result; 
    loop(l, result); 
    l = result; 
} 

Альтернативное решение

Мы также можем сделать это по-другому:

let rec revlist1 l = 
    match l with 
    | [] -> l 
    | x::xs -> (revlist1 xs) @ [x] 

Это в основном говорится, что обратный список переднего элемент исходного списка, приложенного к реверсу остальных.

Перевод алгоритм тарабарщина урожаи формы:

Node* reverse_list1(Node* list) 
{ 
    if(list == NULL) return NULL; // reverse of empty list is empty list. 
    if(list->next == NULL) // last element in list? 
     return list; // the reverse of a list with 1 element is the same. 
    else 
    { 
     Node* head = list; 
     Node* tail = list->next; 
     head->next = NULL; 
     Node* end_of_reverse_tail = tail; // the first will be the last... 
     Node * result = reverse_list1(tail); 
     end_of_reverse_tail->next = head; 
     return result; 
    } 
} 

отметить, что это не является рекурсивным решение хвоста.