反向链表递归

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