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.

- What the previous node was
- 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