扭转链表

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

  }

Answer 2

需要将新尾部（即旧头部）的next指针设置为NULL

编辑：这是一个递归版本

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


    if (child == NULL)
          return parent ;  /* new head */

    new_head = reverse_list_recursive(child)
    child->next = parent; /* Old parent is the new child of the old child when reversed */
    parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */
    return new_head;
}