wake-up-neo.net

Umkehrung einer verknüpften Liste in c

Der folgende Code funktioniert gut, wenn head als Parameter an ihn gesendet wird. Da ich neu bei C bin, konnte ich nicht verstehen, wie es funktioniert. Hilf mir bitte raus.

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. dh) wenn die Links wie sind,

1 -> 2 -> 3 -> 4 

dann hw ist es geändert als,

4 -> 3 -> 2 -> 1
12
rampireram

Der allgemeine rekursive Algorithmus dafür ist:

  1. Divide die Liste in 2 parts - erster Knoten und Rest der Liste.
  2. Rufen Sie rekursiv reverse für die rest der Verknüpften Liste auf.
  3. Verknüpfen Sie rest mit 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:

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

53
codaddict

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.

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

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

}

Mir scheint, dass niemand einen Algorithmus vorgeschlagen hat, der tail-rekursiv ist. Im Prinzip kann ein rekursiver Algorithmus ohne einen Stack kompiliert werden (vorausgesetzt der Compiler ist intelligent genug), wodurch Code erzeugt wird, der weniger Speicher verbraucht.

Angenommen, TList ist ein benutzerdefinierter Datentyp für einfach verknüpfte Liste. Es ist ein Zeiger auf eine Struktur, die als link-Feld für den Zugriff auf das nächste Element in der Liste dient.

Der Algorithmus ist der folgende:

`` `

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

`` `

0
FSp
    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);
}
0
Krishna Durgam

Sei die verknüpfte Liste 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);
}

führen Sie nun die Funktion für die verknüpfte Liste aus 1-> 2-> 3 -> 4

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

liste der Funktion ist
1 (erster) -> 2 (zweiter) -> 3 -> 4

  • inside reverse (& 2) Der Code läuft bis rev_head = reverse (& 3); Funktionsliste
    2 (erster) -> 3 (zweiter) -> 4

  • inside reverse (& 3) Der Code wird ausgeführt, bis rev_head = reverse (& 4); list if function
    3 (erster) -> 4 (zweiter)

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

liste der Funktion 

4(first)-> NULL(second)

  • zurück zur Rückseite (& 3) Liste der Funktionen ist
    NULL <-3 (erster) 4 (zweiter)
    und der zurückgegebene Wert von rev_head = & 4

nach der Ausführung von second-> next = first; Liste wird

NULL <- 3(first) <-4 (zweiter)

return (rev_head); wird ausgeführt, was & 4 durchläuft, weil rev_head = & 4 ist

  • zurück zu rev ​​(& 2)

liste in Funktion ist 

NULL <-2 (erster) 3 (zweiter) <-4 

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

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

NULL <-2 (erster) <-3 (zweiter) <-4

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

  • zurück zu rev ​​(& 1)

liste in Funktion ist 

NULL <-1 (erster) 2 (zweiter) <-3 <-4 

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

nun wird second-> next = first ausgeführt und liste wird

NULL <-1 (erster) <-2 (zweiter) <-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 lange gebraucht, um das zu verstehen und auch diese Antwort zu schreiben. 

0
user7441114

Dies ist ein schöner Ansatz, dem Sie folgen können, 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 folgendermaßen auf:

rec_reverse(NULL, head);

Ansatz:

  • Wenn Sie die Funktion rekursiv aufrufen (Zeile 6), gehen wir zum letzten Knoten der Verknüpften Liste.
  • Dann aktualisieren wir head mit der Adresse des letzten Knotens (Zeile 10).
  • Schließlich zeigen wir die Verbindung jedes Knotens zu seinem vorherigen Knoten (Zeile 7).
0
Amit Upadhyay