代码之家 › 专栏 › 技术社区 › Engineer999

使用递归从尾部反转链接列表

reverse linked-list data-structures recursion c++

Engineer999 · 技术社区 · 6 年前

我仍然在努力使用递归技术来解决这个问题。我知道有更好的方法来解决我下面的问题:颠倒链接列表。我所看到的大多数方法,都是通过使用迭代或递归,从头部到尾部开始反转指针。

我试图通过先递归地查找列表中的最后一个节点,然后每次函数返回时都更改指针来反转列表。

我到底做错了什么?或者这个方法甚至可以工作,而不需要向递归函数传递更多的参数?事先谢谢你的帮助。

struct Node
{
    int data;
    struct Node *next;
};

Node* Reverse(Node *head)
{
    static Node* firstNode = head;
    // if no list return head
    if (head == NULL)
    {
        return head;
    }

    Node* prev = NULL;
    Node* cur = head;

    // reached last node in the list, return head
    if (cur->next == NULL)
    {
        head = cur;
        return head;
    }

    prev = cur;
    cur = cur->next;
    Reverse(cur)->next = prev;

    if (cur == firstNode)
    {
        cur->next = NULL;
        return head;
    }
    return cur;
}

编辑:另一次尝试

Node* ReverseFromTail(Node* prev, Node* cur, Node** head);

Node* ReverseInit(Node** head)
{
    Node* newHead = ReverseFromTail(*head, *head, head);
    return newHead;
}



Node* ReverseFromTail(Node* prev, Node* cur, Node** head)
{
    static int counter = 0;
    counter++;

    // If not a valid list, return head
    if (head == NULL)
    {
        return *head;
    }

    // Reached end of list, start reversing pointers
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }


    Node* retNode = ReverseFromTail(cur, cur->next, head);
    retNode->next = cur;


    // Just to force termination of recursion when it should. Not a permanent solution 
    if (counter == 3)
    {
        cur->next = NULL;
        return *head;
    }

    return retNode;
}

最终解决了:

Node* NewestReverseInit(Node* head)
{
    // Invalid List, return
    if (!head)
    {
        return head;
    }

    Node* headNode = NewestReverse(head, head, &head);

    return headNode;
}

Node* NewestReverse(Node *cur, Node* prev, Node** head)
{
    // reached last node in the list, set new head and return
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }

    NewestReverse(cur->next, cur, head)->next = cur;

    // Returned to the first node where cur = prev from initial call
    if (cur == prev)
    {
        cur->next = NULL;
        return *head;
    }

    return cur;
}

3 回复 | 直到 6 年前

schwrz 6 年前

下面是我在5分钟内写的一个完整的实现:

#include <stdio.h>

struct Node
{
     int data;
     struct Node *next;
};

struct Node* Reverse(struct Node *n)
{
    static struct Node *first = NULL;

    if(first == NULL)
      first = n;

    // reached last node in the list
    if (n->next == NULL)
      return n;

    Reverse(n->next)->next = n;

    if(n == first)
    {
      n->next = NULL;
      first = NULL;     
    }

    return n;
}

void linked_list_walk(struct Node* n)
{
  printf("%d", n->data);
  if(n->next)
    linked_list_walk(n->next);
  else
    printf("\n");
}

int main()
{
  struct Node n[10];
  int i;

  for(i=0;i<10;i++)
  {
    n[i].data = i;
    n[i].next = n + i + 1;
  }
  n[9].next = NULL;

  linked_list_walk(n);
  Reverse(n);
  linked_list_walk(n+9);
}

输出:

0123456789                                                                                                                                                                          
9876543210

SergeyA 6 年前

我不会给你密码,我会给你这个主意。您可以在代码中实现这个想法。

所有递归问题的关键是找出两种情况:重复步骤和结束情况。一旦你这样做,它的工作几乎就像魔术一样。

将此原则应用于反转链接列表:

结束案例:一个元素的列表已经颠倒(这很简单),并返回元素本身。
重复情况:给定列表l,反转这至少意味着反转l“,其中l'是l'是没有第一个元素的列表(通常称为 head ,而不是将头部添加为列表的最后一个元素。返回值将与刚刚进行的递归调用的返回值相同。

Robert Andrzejuk 6 年前

这是可以做到的。理解递归的关键是 起点是什么?

通常我会创建一个 “开始” 准备第一次调用的函数。有时它是一个独立的函数(就像在底层的非OO实现中)。有时它只是一个特殊的第一次调用(如下面的示例)。

另外,关键是在变量改变前记住它们,什么是 new head .

新的 head 是列表的最后一个元素。所以你必须把它从列表的底部拿出来。

这个 next 元素始终是您的父元素。

那么诀窍就是按正确的顺序做每件事。

    Node* Reverse( Node* parent) // Member function of Node.
    {
        Node* new_head = next ? next->Reverse( this ) 
                              : this;

        next = parent;

        return new_head;
    }

调用函数时使用: var.Reverse( nullptr);

例子:

int main()
{
    Node d{ 4, nullptr };
    Node c{ 3, &d };
    Node b{ 2, &c };
    Node a{ 1, &b };

    Node* reversed = a.Reverse( nullptr );
}

那么这里发生了什么?

首先,我们创建一个链接列表:

 a->b->c->d->nullptr

然后函数调用:

a.Reverse(nullptr) 被调用。
这叫 Reverse 在下一个节点上 b.Reverse 与父级 a .
这叫 反向 在下一个节点上 c.Reverse 与父级 b .
这叫 反向 在下一个节点上 d.Reverse 与父级 c .
d 没有 下一个 节点,所以它表示新的头是它自己。
D 的 下一个 现在是父母了吗 C
D 将自身作为 new_head .
返回 C : 新的头 从返回 D 是 D
C 的 下一个 现在是父母了吗 乙
C 返回 新的头 它是从 D
返回 乙 : 新的头 从返回 C 是 D
乙 的 下一个 现在是父母了吗 一
乙 返回 新的头 它是从 C
返回 一 : 新的头 从返回 乙 是 D
一 的 下一个 现在是父母了吗 nullptr
一 返回 新的头 它是从 乙
D 已返回

非面向对象实现;

Node* reverse_impl(Node* parent)
{
    Node* curr = parent->next;
    Node* next = curr->next;

    Node* new_head = next ? reverse_impl( curr ) 
                          : curr;

    curr->next = parent;

    return new_head;
}

Node* reverse(Node* start)
{
    if ( !start )
        return nullptr;

    Node* new_head = reverse_impl( start );
    start->next    = nullptr;

    return new_head;
}