Reverse a Linked List.Node *ReverseLinkedListIterative(Node *n)
{
Node *priv = nullptr;
Node *temp = nullptr;
while (nullptr != n)
{
temp = n->next;
n->next = priv;
priv = n;
n = temp;
}
return priv;
}
// Input: head->n->n->n->nullptr
// We will solve recursively as follows:
// nullptr<-head<-[ReverseLinkedListRecursive(head->next)]
Node *ReverseLinkedListRecursive(Node *n)
{
if (nullptr == n || nullptr == n->next)
return n;
// Note that before we cut off the rest of the list from the head and send
// it to this function recursively n->next which is now the head of the rest
// of the list, will become the tail after the function returns, so we record it now
Node *rest_tail = n->next;
Node *rest_head = ReverseLinkedListRecursive(n->next);
// Now we have a head and a tail for the rest of the list so n, which is the old head
// is now the tail and will point to nullptr and rest's tail will point to it
n->next = nullptr;
rest_tail->next = n;
return rest_head;
} |