Given a Singly linked list as input, Reverse it.
InputYou 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.
OutputYour 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.
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