反向链接列表递归

Question

我在链表定义为一个节点：

typedef struct abc 
{ 
    int id; 
    struct abc *next;   
}node; 

我要反向链接列表recursively.I想过去的头指针功能。我的功能定义如下：

node *reverseLinkedListRecursively(node *head) 
{ 
    node *current; 
    node *rest; 
    if(head == NULL) 
     return head; 

    current=head; 
    rest=head->next; 

    if(rest == NULL) 
    { 
     return rest; 
    } 
    reverseLinkedListRecursively(rest); 
    current->next->next=rest; 
    current->next=NULL; 
    return rest; 
} 

我该如何继续？我已经实现了迭代方法。

Answer 1

如果要扭转一个列表，你必须有一个节点的指针在您的节点结构：

typedef struct abc 
{ 
    int id; 
    struct abc *next; 
    struct abc *prev;   
}node; 

和您的列表必须指向头部和尾部：

typedef struct list 
{ 
    node * first; 
    node * last; 
} list; 

Answer 2

它应该工作如下：

node *reverseLinkedListRecursively(node *rest, node *reversed) 
{ 
    node *current; 

    if (rest == NULL) 
     return reversed; 

    current = rest; 
    rest = rest->next; 
    current->next = reversed; 

    return reverseLinkedListRecursively(rest, current); 
} 

最初，从：

reverseLinkedListRecursively(linkedList, NULL); 

BTW：这个函数是尾递归的。所以一个最先进的编译器应该能够把这个递归解决方案变成一个更有效的迭代解决方案。

Answer 3

要递归地反转链接列表，我们反转（递归）由除第一个节点以外的所有内容组成的子列表，然后将第一个节点放在末尾。为了将第一个节点放在最后，我们需要递归调用来返回指向最后一个节点的指针，以便我们可以访问它的next成员。当子列表为空时，我们停止递归，并返回当前节点。在我们将第一个节点附加到递归调用结果的末尾之后，当我们从当前递归调用返回时，第一个节点是“最后一个节点”。最后有一个细节：原始的第一个节点（现在的最后一个）仍然指向原始的第二个节点（现在是倒数第二个）。我们需要将它解决为空，因为它现在是列表的结尾。

这样：

node* reverseLinkedListHelper(node* head) { 
    if (head->next == NULL) { return head; } 
    node* last = reverseLinkedListRecursively(head->next); 
    last->next = head; 
    return head; 
} 

void reverseLinkedList(node* head) { 
    assert (head != NULL); 
    reverseLinkedListHelper(head); 
    head->next = NULL; 
} 

还有一个问题，我会让你思考：我们如何获得一个指向该列表的新头？ :)

Answer 4

node *reverseLinkedListRecursively(node *head) 
{ 
    node *current; 
    node *rest; 
    if(head == NULL) 
     return head; 


    current=head; 
    rest=head->next; 

    if(rest == NULL) 
    { 
     /* Wrong. Think about the simple case of a one-element list. 
      Your code will return NULL as the reversed list. */ 
     //return rest; 
     return current; 
    } 
    /* You lost the return value, which will be the beginning of the reversed 'rest'. */ 
    //reverseLinkedListRecursively(rest); 
    rest = reverseLinkedListRecursively(rest); 

    /* current->next points to the last element in the reversed 'rest'. 
     What do you want that to point to? */ 
    //current->next->next=rest; 
    current->next->next = current; // temporarily circular 
    current->next=NULL; 

    /* Now you can return rest, since you set it to the beginning of the reversed list. */ 
    return rest; 
} 

Answer 5

对于每个递归，跟踪当前节点和其余节点的前端。其余为NULL时返回。递归返回后，反转下一个“休息”字段指向当前。为了跟踪新的第一个节点，递归函数只传递旧的最后一个节点。

void recursive_reverse() { 
    // driver for the recursive reverse function. 
    // first is a data member of linked list that point to the first node of list. 
    first = recursive_reverse(first, first->next); 
} 

Node* recursive_reverse(Node *current, Node *rest) { 
    // if rest == NULL, the current must be the old last node, 
    // which is also the new first node 
    if (rest == NULL) return current; 
    Node *new_first = recursive_reverse(current->next, rest->next); 

    // rearrange pointers 
    rest->next = current; 
    current->next = NULL; 

    // pass along the new first node 
    return new_first; 
} 

我的原始实现使用了一个sentinel节点，所以我没有在这里测试代码。抱歉!只要将它看作伪代码即可。

Answer 6

void RecursiveReverse(struct node** headRef) 
{ 
    struct node* first; 
    struct node* rest; 

    if (*headRef == NULL) return; // empty list base case 

    first = *headRef; // suppose first = {1, 2, 3} 
    rest = first->next; // rest = {2, 3} 

    if (rest == NULL) return; // empty rest base case 
    RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case after: rest = {3, 2} 

    first->next->next = first; // put the first elem on the end of the list 
    first->next = NULL; // (tricky step -- make a drawing) 

    *headRef = rest; // fix the head pointer 
} 

Answer 7

嘿家伙找到倒转链表的方案，有和没有递归下面，希望这会帮助你。

LINK *reverse_linked_list_recursion(LINK *head) 
{ 
     LINK *temp; 
     if (!head) { 
       printf("Empty list\n"); 
       return head; 
     } 
     else if (!head->next) 
       return head; 
     temp = reverse_linked_list_recursion(head->next); 
     head->next->next = head; 
     head->next = NULL; 
     return temp; 
} 

LINK *reverse_linked_list_without_recursion(LINK *head) 
{ 
     LINK *new, *temp; 
     if (!head) { 
       printf("No element in the list\n"); 
       return head; 
     } 
     else { 
       new = head; 
       while (head->next) { 
         temp = head->next; 
         head->next = temp->next; 
         temp->next = new; 
         new = temp; 
       } 
     } 
     return new; 
}