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”指针调用 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);

Answer 2

这可能会有所帮助

List
{
public:

    .....

    void plzReverse()
    {
         Node* node = myReverse(head);
         node->next = NULL;
    }

private:

    Node * myReverse(Node * node)
    {
        if(node->next == NULL)
        {
            head = node;
            return node;
        }
        else
        {
            Node * temp = myReverse(node->next);
            temp ->next = node;
            return node;
        }
     }
}

另一种解决方案可能是：

List
{
public:
.....

    void plzReverse()
    {
        Node* node = myReverse(head, head);
        node->next = NULL;
    }

private:

    Node * myReverse(Node * node, Node*& rhead)
    {
        if(node->next == NULL)
        {
            rhead = node;
            return node;
        }
        else
        {
            Node * temp = myReverse(node->next,rhead);
            temp ->next = node;
            return node;
        }
     }
}

Answer 3

这就是你需要的：

Node* reverse(Node* p) {
  if (p->next == NULL) {
    return p;
  } else {
    Node* t = reverse(p->next); // Now p->next is reversed, t is the new head.
    p->next->next = p; // p->next is the current tail, so p becomes the new tail.
    p->next = NULL;
    return t;
  }
}

Answer 4

The recursive solution can look quite pretty, even in C++:

Node* reverse(Node* pivot, Node* backward = 0) {
  if (pivot == 0)  // We're done
    return backward; 
  // flip the head of pivot from forward to backward
  Node* rest = pivot->next;
  pivot->next = backward;
  // and continue
  return reverse(rest, pivot);
}

Most C++ compilers do tail call optimization so there's no reason to believe this to be less efficient than an iterative solution.

Answer 5

linkedList *reverseMyNextPointer(linkedList *prevNode, linkedList *currNode)
{
    linkedList *tempPtr;
    if(!currNode)
        return prevNode; 
    else
    {
        tempPtr = currNode->next;
        currNode->next = prevNode;
        return reverseMyNext(currNode,tempPtr);
    }
}

head = reverseMyNextPointer(nullptr,head);

Answer 6

这是将返回值保留为 void 的解决方案。

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