Реверсивный реверсивный связанный список в c

Question

Следующий код прекрасно работает, когда head отправляется в качестве параметра. Поскольку я новичок в C, я не мог понять, как это работает. Помоги мне, пожалуйста.

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

Я не знаю, как ссылки предоставляются с помощью этих рекурсивных вызовов. т.е. если ссылки такие же,

1 -> 2 -> 3 -> 4 

тогда как это изменилось,

4 -> 3 -> 2 -> 1

Answer 1

Общий рекурсивный алгоритм для этого:

1. Divide список в 2 части - первый узел и остальная часть списка.
2. Рекурсивно вызывать реверс для rest связанного списка.
3. Ссылка на сайт rest в first,
4. исправлять head указатель

Вот код с встроенными комментариями:

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

Я надеюсь, что эта картина прояснит ситуацию:

http://geeksforgeeks.org/wp-content/uploads/2009/07/Linked-List-Rverse.gif.

Answer 2

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

struct node *head;
void reverse(struct node *prev, struct node *cur)
{
   if(cur){
      reverse(cur,cur->link);
      cur->link = prev;
    }
    else{
      head = prev;
    }
}

В основном, обратный вызов (NULL, голова);

Answer 3

/* Reverses a linked list, returns head of reversed list
*/
NodePtr reverseList(NodePtr curr) {
    if (curr == NULL || curr->next == NULL) return curr; // empty or single element case

    NodePtr nextElement = curr->next;
    curr->next = NULL;
    NodePtr head = reverseList(nextElement);
    nextElement->next = curr;
    return head;
}

Answer 4

Другое решение:

struct node *reverse_recur(struct node *temp)
{
    if(temp->link==NULL)
    {
        return temp;
    }

    struct node *temp1=temp->link;

    temp->link=NULL;

    return (reverse_recur(temp1)->link=temp);

}

Answer 5

Пусть связанный список будет 1-> 2 -> 3 ->4

функция в с...

struct linked_node * reverse_recursive(struct linked_node * head)
{
struct linked_node * first;/*stores the address of first node of the linked
list passed to function*/
struct linked_node * second;/* stores the address of second node of the
linked list passed to function*/
struct linked_node * rev_head;/*stores the address of last node of initial 
linked list. It also becomes the head of the reversed linked list.*/
//initalizing first and second
first=head;
second=head->next;
//if the linked list is empty then returns null
if(first=NULL)
   return(NULL);
/* if the linked list passed to function contains just 1 element, then pass
address of that element*/
if(second==NULL)
   return(first);
/*In the linked list passed to function, make the next of first element 
 NULL. It will eventually (after all the recursive calls ) make the
 next of first element of the initial linked list NULL.*/
first->next=NULL;
/* storing the address of the reverse head which will be passed to it by the
 condition if(second==NULL) hence it will store the address of last element
 when this statement is executed for the last time. Also here we assume that 
the reverse function will yield the reverse of the rest of the linked 
list.*/
rev_head=reverse(second);
/*making the rest of the linked list point to the first element. i.e. 
 reversing the list.*/
second->next=first;

/*returning the reverse head (address of last element of initial linked 
list) . This condition executes only if the initial list is 1- not empty 
2- contains more than one element. So it just relays the value of last 
element to higher recursive calls.  */
return(rev_head);
}

теперь запускается функция для связанного списка 1-> 2-> 3 -> 4

• внутри реверса (&1) код выполняется до тех пор, пока rev_head= реверс (&2); // здесь & 1 адрес 1.

список функций
1(первый)->2(второй) -> 3 -> 4

• внутренний обратный (& 2) код выполняется до тех пор, пока rev_head=reverse(&3); список функций
  2 (первый)->3 (второй) -> 4

• внутренний обратный (& 3) код выполняется до тех пор, пока rev_head=reverse (&4); список если функция
  3 (первый) -> 4 (второй)

• внутреннее обратное (& 4) условие завершения second==NULL - true, поэтому return выполняется и возвращается адрес 4.

список функций

4 (первый)-> NULL(второй)

• назад к обратному (& 3) список функций
  NULL<-3 (первый) 4 (второй)
  и значение rev_head=&4, которое было возвращено

после выполнения second->next=first; список становится

NULL<- 3 (первый) <-4 (второй)

возврат (rev_head); выполняется, который проходит & 4, потому что rev_head=&4

• вернуться к обороту (& 2)

список в функции

NULL<-2 (первый) 3 (второй) <- 4

и rev_head это & ​​4, который был возвращен rev (& 3)

после выполнения second-> next = first список становится

NULL<-2 (первый) <- 3 (второй) <- 4

возвращать (rev_head); выполняется, который возвращает & 4 к обороту (&1);

• вернуться к обороту (&1)

список в функции

NULL<-1(первый) 2 (второй) <- 3 <-4

и значение rev_head равно & 4, которое было передано в обратном порядке (& 3)

теперь second-> next = first выполняется и список становится

NULL<-1(первый) <- 2 (второй) <- 3 <-4

возвращать (rev_head); выполняется // rev_head=&4, который был возвращен реверсом (& 2), а значение rev_head передается главной функции.

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

Answer 6

Мне кажется, что никто не предложил алгоритм с хвостовой рекурсией. В принципе, хвостовой рекурсивный алгоритм может быть скомпилирован без стека (при условии, что компилятор достаточно умен), создавая таким образом код, который потребляет меньше памяти.

Предполагать TList является пользовательским типом данных для односвязного списка, это указатель на структуру, которая как link поле для доступа к следующему элементу в списке.

Алгоритм следующий:

`` `

TList reverse_aux(TList l, TList solution) {
    if (l == NULL) {
        return solution;
    } else {
        TList tmp = l->link;
        l->link = solution;
        return reverse_aux(tmp, l);
    }
}

TList reverse(TList l) {
    return reverse_aux(l, NULL);
}

`` `

Answer 7

ll *rev_list(ll *prev, ll *cur)
{
    if (!cur) {
        return prev;
    }

    ll *tmp = cur;
    cur = cur->next;
    tmp->next = prev;
    prev = tmp;
    return rev_list(prev, cur);
}

Найдите полный код: https://github.com/vijaythreadtemp/Data-Structures-And-Algorithms/blob/master/rev_link_list_rec.cxx

Answer 8

Это прекрасный подход для рекурсивного изменения SLL:

1.    struct node* head; // global head
2.    void rec_reverse(struct node* prev, struct node* cur)
3.    {
4.        if (cur)
5.        {
6.            rec_reverse(cur, cur->next);
7.            cur->next = prev;
8.        }
9.        else
10.            head = prev;
11.    }

Вызовите функцию следующим образом:

rec_reverse(NULL, head);

Подход:

• Вызывая функцию рекурсивно (строка 6), мы переходим к последнему узлу связанного списка.
• Затем мы обновляем заголовок адресом последнего узла (строка 10).
• Наконец, мы указываем ссылку каждого узла на его предыдущий узел (строка 7).

Answer 9

    To fix head also:

void reverse_list_recursive_internal (struct list **head, struct list *node)
{
    /* last node, fix the head */
    if (node->next == NULL) {
        *head = node;
        return; 
    }
    reverse_list_recursive_internal(head, node->next);
    node->next->next = node;
    node->next = NULL;
}

void reverse_list_recursive (struct list **head)
{
    if (*head == NULL) {
        return;
    }
    reverse_list_recursive_internal(head, *head);
}