Given a Singly linked list as input, Reverse it.

You only need to write a function named "Reverse" that should take pointer to the head of linked list as argument and return pointer to the head node after reversal.

Your function must return pointer to the head of linked list after reversal.

Here we implement reversing a Singly linked list. We need to keep track of two extra informations here.

1. What the previous node was
2. What's the next node.

In the final linked-list, the previous element becomes the next node. So we update the next pointer of each node with it's previous node's address.

The new head of the linked list is the last node of the original list. After traversing the list, current node will point to NULL and the previous_node will point to the last element.

That was the idea. Now let's see step by step how the code works.

We iterate over each node, current_node stores my current position, and prev_node and next_node stores the corresponding pointer to the previous and next elements.

When my current_node is NULL, we know that the end of the list is reached. Once we finish processing this node, we move forward. This loop will take care of that.

while(current_node!=NULL)
{
    current_node=next_node;
}

Since we will be changing the current_node->next_node information of the current_node, let's store the current value in next_node since we need it to iterate forward. Now that information is backed up, to reverse the list, we update current_node->next_node with the address of previous_node. In the end update the prev_node with current_node before you move forward.

        next_node = current_node->next_node;
        current_node->next_node = prev_node;
        prev_node = current_node;

In the end assign head with the address of the last element in the list and return it.

Time Complexity: O(n) to traverse the list once.

Space Complexity: O(1) 3 Extra Variables to keep track of the current, next and previous nodes.

editorial written by ash1794

Node* Reverse(Node* head)
{
    Node* current_node = head; // Keeps track of the current Node
    Node* prev_node = NULL,next_node;// Previous and next node
    
    while(current_node!=NULL)
    {
        
        // Next Node in the original list
        next_node = current_node->next_node;
        // Update the current_node with the previous node pointer
        current_node->next_node = prev_node;
        // Update Previous Node
        prev_node = current_node;
        // Traverse Forward
        current_node = next_node;
    }
    head = prev_node;   //The last node visited is the new head.
    return head;
}

featured solution by ash1794