c - 反向链表

Question

我正在尝试使用递归反转链表并为其编写了以下代码。该列表是列表的开头。

 node *reverse_list_recursive(node *list)
 {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           current->next = parent;
           printf("\n %d  %d \n",current->value,parent->value);
           return parent;
       }

  }

我可以看到所有链接都被反转了。但是，当我尝试显示时，我得到了无限的数字打印。当我试图反转列表中最初的第一个数字的链接时，我怀疑有错误。

我做错了什么？

Answer 1

假设我有一个链表:

 ----------      ----------      ----------      ---------- 
|  1  |    |--->|  2  |    |--->|  3  |    |--->|  4  |    |--->NULL
 ----------      ----------      ----------      ---------- 

您的代码将其转换为:

   ----------------------          ----------------------
   |                    |          |                    |
   v                    |          v                    |
 ----------      ----------      ----------      ----------
|  1  |    |--->|  2  |    |    |  3  |    |    |  4  |    | 
 ----------      ----------      ----------      ---------- 
                   ^                    |
                   |                    |
                   ----------------------

注意第一个元素仍然指向 2。

如果在前两个之后添加 parent->next = NULL 行，您将得到:

           ----------------------          ----------------------
           |                    |          |                    |
           v                    |          v                    |
         ----------      ----------      ----------      ----------
NULL<---|  1  |    |    |  2  |    |    |  3  |    |    |  4  |    | 
         ----------      ----------      ----------      ---------- 
                           ^                    |
                           |                    |
                           ----------------------

这实际上是正确的结构。

完整代码为:(每次递归调用只需要打印当前值即可)

node *reverse_list_recursive(node *list)
  {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           parent->next = NULL;
           current->next = parent;
           printf("\n %d \n",current->value);
           return parent;
       }

  }