递归反向链表

我试图使用指针指针递归地执行反向链表，但问题是在第二个循环中脚本崩溃。 你能帮助我解决我的问题吗？ 这是我的代码：

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

应该遵循的方式是：

  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 2

试试这个

 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 3

您需要在reverseNumber调用中将指针传递给指针（current-> next）。 它应该是reverseNumber（＆（current-> next））。 我想你不是要回头了。 此外，反向清单将提前结束。 例如，如果列表为1-> 2-> 3-> 4-> 5-> NULL，则反转后将为5-4-> NULL。

Answer 4

我不明白为什么双指针。 它没有任何目的。 所以，我实际上写了一个简单的程序，做你需要的。

假设这将是你的Mynbr的结构

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

键入定义结构

  typedef struct Mynbr Mynbr_t; 

我的链表反转function就像这样（递归调用）

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

继续，测试它，使用下面的代码。 它只是反转列表。

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