c++ - 递归反向单链表

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 设置为 previous。查看recursive version here举个例子。来自链接:

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