Part 3 of 26 in Linked List - set 02

Problem statement

Given a Singly linked list as input, Reverse it.

Input

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.

Output

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