反向鏈接列表遞歸

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