在c中递归地反转链表

Question

当head作为参数发送给它时,以下代码可以正常工作.由于我是C的新手,我无法理解它是如何工作的.请帮帮我.

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

我不知道如何使用这些递归调用提供链接.即)如果链接为,

1 -> 2 -> 3 -> 4 

然后hw被改变为,

4 -> 3 -> 2 -> 1

Answer 1

一般的递归算法是:

1. Divide2部分列表- 第一个节点和列表的其余部分.
2. 递归调用rest链接列表的反向.
3. 链接rest到first.
4. 修复head指针

以下是带内联注释的代码:

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

我希望这张照片能让事情变得更清晰:

图片http://geeksforgeeks.org/wp-content/uploads/2009/07/Linked-List-Rverse.gif.

Answer 2

替代解决方案:

struct node *head;
void reverse(struct node *prev, struct node *cur)
{
   if(cur){
      reverse(cur,cur->link);
      cur->link = prev;
    }
    else{
      head = prev;
    }
}

在main中,调用reverse(NULL,head);