рекурсивно реверсировать связанный список - подпись другой функции - PullRequest
Новая
       5

рекурсивно реверсировать связанный список - подпись другой функции

0 голосов
/ 12 декабря 2011

Есть много сообщений, вероятно, с тем же вопросом, но проблема говорит, что это должно быть сделано 

 node* reverseList (node * lh)
                              {
                               if(lh==NULL)............ ;

                                else if (lh->next==NULL)...........;

                                else ...........;
                              }

три пробела должны быть заполнены первые два просто 

return NULL

и 

return lh

repectively

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

Ответы [ 3 ]

3 голосов
/ 12 декабря 2011

Хитрость в решении рекурсивных проблем - притворяться, что вы уже закончили. Чтобы решить эту домашнюю работу самостоятельно, вам нужно ответить на три вопроса:

  • Как перевернуть пустой список? (то есть список с lh, установленным на NULL)?
  • Как перевернуть список только с одним элементом?
  • Если кто-то может перевернуть все элементы в списке, кроме начального для вас, где вы добавляете первый элемент из начального списка в предварительно перевернутую «хвостовую» часть списка?

Вы уже ответили на первые два вопроса: NULL и lh - правильные ответы. Теперь подумайте о третьем: 

else {
    node *reversedTail = reverseList(lh->next);
    ...
}

На данный момент, reversedTail содержит предварительно перевернутый хвост вашего списка. Все, что вам нужно сделать, это установить lh-> рядом с NULL, добавить его в конец списка, который вы держите, и вернуть reversedTail. Окончательный код выглядит так: 

else {
    node *reversedTail = reverseList(lh->next);
    node *p = reversedTail; 
    while (p->next) p = p->next;
    p->next = lh;
    lh->next = NULL;
    return reversedTail;
}
2 голосов
/ 12 декабря 2011

Я думаю, что это отвечает: 

node *reverseList(node *lh)
{
    if (!lh) return NULL;
    else if (!lh->next) return lh;
    else {
        node *new_head = reverseList(lh->next);
        lh->next->next = lh;
        lh->next = NULL;
        return new_head;
    }
}

Возвращает начало перевернутого списка, то есть хвост исходного списка. 

head = reverse_list(head);
1 голос
/ 12 декабря 2011

Ниже приведен API, который выполняет обращение к Единому связанному списку, это один из лучших алгоритмов, которые я видел: 

void iterative_reverse() 
{ 

    mynode *p, *q, *r; 

    if(head == (mynode *)0) 
    { return; 
    } 

    p = head; 
    q = p->next; 
    p->next = (mynode *)0; 

    while (q != (mynode *)0) 
    { 
        r = q->next; 
        q->next = p; 
        p = q; 
        q = r; 
    } 
    head = p; 
 }
...