Rekursives Umkehren einer verketteten Liste in c

Der folgende Code funktioniert einwandfrei, wenn head als Parameter an ihn gesendet wird. Da ich neu in C bin, konnte ich nicht verstehen, wie es funktioniert. Helfen Sie mir bitte.

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;
}

Ich weiß nicht, wie die Links mit diesen rekursiven Aufrufen bereitgestellt werden. ie) wenn die Links so sind,

1 -> 2 -> 3 -> 4 

dann ist es geändert als,

4 -> 3 -> 2 -> 1

Der allgemeine rekursive Algorithmus dafür lautet:

1. Divide die Liste ein 2 parts – erster Knoten und Rest der Liste.
2. Rufen Sie rekursiv reverse für die auf rest der verknüpften Liste.
3. Verknüpfung rest zu first.
4. Fix head Zeiger

Hier ist der Code mit Inline-Kommentaren:

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.
}

Ich hoffe, dieses Bild wird die Dinge klarer machen:

_{(Quelle: geeksforgeeks.org)}

.

Alternative Lösung:

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

Rufen Sie in der Hauptsache reverse(NULL,head) auf;

/* 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;
}

Die verknüpfte Liste sei 1 -> 2 -> 3 -> 4

die Funktion in c ist–

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);
}

Jetzt läuft die Funktion für die verknüpfte Liste 1-> 2-> 3 -> 4

• innerhalb von reverse(&1) läuft der Code bis rev_head=reverse(&2); // hier ist &1 die Adresse 1.

Liste der Funktion ist
1 (erste) -> 2 (zweite) -> 3 -> 4

• innerhalb reverse(&2) Code läuft bis rev_head=reverse(&3); Liste der Funktion
  2 (erster) -> 3 (zweiter) -> 4

• innerhalb reverse(&3) Code läuft bis rev_head=reverse (&4); list if-Funktion
  3 (erster) -> 4 (zweiter)

• innerhalb von reverse(&4) ist die Beendigungsbedingung second==NULL wahr, also wird return ausgeführt und die Adresse 4 zurückgegeben.

Liste der Funktion

4 (erste) -> NULL (zweite)

• zurück zur Umkehr(&3)-Liste der Funktion ist
  NULL<-3 (erste) 4 (zweite)
  und der Wert von rev_head=&4, der zurückgegeben wurde

nach dem Ausführen von second->next=first; Liste wird

NULL<- 3 (erste) <-4 (zweite)

Rückkehr (rev_head); wird ausgeführt, was &4 übergibt, weil rev_head=&4

• zurück zu rev(&2)

Liste in Funktion ist

NULL<-2(erste) 3(zweite)<-4

und rev_head ist &4, was von rev(&3) zurückgegeben wurde

Nach dem Ausführen von second->next=first wird list zu

NULL<-2(erste)<-3(zweite)<-4

return(rev_head); wird ausgeführt, was &4 zu rev(&1) zurückgibt;

• zurück zu rev(&1)

Liste in Funktion ist

NULL<-1(erste) 2(zweite)<-3<-4

und der Wert von rev_head ist &4, was von reverse(&3) übergeben wurde.

jetzt wird second->next =first ausgeführt und list wird

NULL<-1(erste) <- 2(zweite)<-3<-4

return(rev_head); wird ausgeführt // rev_head=&4, das von reverse(&2) zurückgegeben wurde, und der Wert von rev_head wird an die Hauptfunktion übergeben.

hoffe das hilft. Ich habe ziemlich viel Zeit gebraucht, um das zu verstehen und auch diese Antwort zu schreiben.

Eine andere Lösung:

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);

}

Dies ist ein schöner Ansatz, dem man folgen kann, um SLL rekursiv umzukehren:

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.    }

Rufen Sie die Funktion so auf:

rec_reverse(NULL, head);

Sich nähern:

• Durch rekursiven Aufruf der Funktion (Zeile 6) gehen wir zum letzten Knoten der verketteten Liste.
• Dann aktualisieren wir head mit der Adresse des letzten Knotens (Zeile 10).
• Schließlich zeigen wir den Link jedes Knotens auf seinen vorherigen Knoten (Zeile 7).

    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);
}