递归反向单链接列表

Question

我试图写一个基本函数,它反转一个递归的单链表.我想知道我是否以正确的方法解决了这个问题？也许有人可以给我一些指示.

 void reverse(Node*& p) {
  if (!p) return;
  Node* rest = p->next;
  if (!rest) return;
  reverse(rest);
  p->next->next = p;
  p->next = NULL;
  p = rest;
}

Answer 1

这不是最有效的方法,但要做到这一点,你可以使用"next"指针调用reverse方法,直到没有下一个.在那里,设置在前一个旁边.从递归返回后,设置在上一个旁边.有关示例,请参阅此处的递归版本.从链接:

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        previous->next = NULL;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);