反向鏈表遞歸

Question

我想做一個反向鏈表，遞歸地使用指針指針，但問題是，在第二個循環腳本崩潰。你能幫助我解決我的問題嗎？這是我的代碼：

void reverseNumber(Mynbr** start){ 
    Mynbr *header; 
    Mynbr *current; 

    if ((*start)){ 
     header = (*start); 
     current = (*start)->next; 

     if (current && current->next!= NULL) 
     { 
      reverseNumber(current->next); 
      header = current; 
      current->next->next = current; 
      current->next = NULL; 
     } 
    } 

} 

Answer 1

您需要將指針傳遞給reverseNumber（current-> next）的調用中的指針。它應該是反向號碼（&（current-> next））。我想你並沒有回到新的頭上。另外，反向列表將提前結束。例如，如果列表是1-> 2-> 3-> 4-> 5-> NULL，那麼在反向之後它將是5-4-> NULL。

Answer 2

應遵循的方法是：

1) Divide the list in two parts - first node and rest of the linked list. 
    2) Call reverse for the rest of the linked list. 
    3) Link rest to first. 
    4) Fix head pointer 

void reverseNumber(struct Mynbr** start) 
{ 
    struct Mynbr* head; 
    struct Mynbr* rest; 

    /* empty list */ 
    if (*start == NULL) 
     return; 

    /* suppose head = {1, 2, 3}, rest = {2, 3} */ 
    head = *start; 
    rest = head->next; 

    /* List has only one node */ 
    if (rest == NULL) 
     return; 

    /* reverse the rest list and put the head element at the end */ 
    reverseNumber(&rest); 
    head->next->next = head; 

    /* tricky step -- see the diagram */ 
    head->next = NULL;   

    /* fix the head pointer */ 
    *start = rest;    
} 

Answer 3

試試這個

void reverseNumber(Mynbr **start){ 
    Mynbr *header = *start; 
    if(!header) return; 
    Mynbr *current = header->next; 
    if(!current) return; 

    header->next = NULL; 
    Mynbr *new_head = current; 
    reverseNumber(&new_head); 
    current->next = header; 
    *start = new_head; 
} 

Answer 4

我不明白爲什麼雙指針。它沒有任何目的。所以，我已經寫了一個簡單的程序來做你需要的。

假設這將是確定結構

typedef struct Mynbr Mynbr_t; 

我的鏈表倒車功能將是這樣的（這是遞歸調用）

void reverseNumber(Mynbr_t* start) { 
     if (start == NULL) return; 
     static Mynbr_t* head; 
     Mynbr_t* current = start; 
     if (current->next != NULL) { 
      reverseNumber(current->next); 
      head->next = current; 
      head = current; 
      head->next = NULL; 
     } else 
      head = current; 
    } 

您的 Mynbr

struct Mynbr { 
     int k; 
     struct Mynbr* next; 
    }; 

類型的結構

繼續，使用下面的代碼進行測試。它只是顛倒了名單。

int main() { 
     size_t Mynbr_size = sizeof(Mynbr_t); 
     Mynbr_t* start = (Mynbr_t*) malloc(Mynbr_size); 
     Mynbr_t* current = start; 
     int i; 
     for (i=0; i<10; i++) { 
      current->k = i; 
      if (i!=9) { 
       current->next = (Mynbr_t*) malloc(Mynbr_size); 
       current = current->next; 
      } 
     } 

     current = start; 
     Mynbr_t* last = NULL; 
     while (current != NULL) { 
      printf("%d\n", current->k); 
      current = current->next; 
      if (current != NULL) 
       last = current; // you need to grab this to loop through reverse order 
     } 

     reverseNumber(start); 

     current = last; 
     while (current != NULL) { 
      printf("%d\n", current->k); 
      current = current->next; 
     } 

     current = last; 
     Mynbr_t* temp; 
     while (current->next != NULL) { 
      temp = current; 
      current = current->next; 
      free(temp); // always free the allocated memory 
     } last = NULL; 
     return 0; 
    }