Reverse linked list!!

Reverse linked list is the one of the most common question in C/C++ interview question. Generally we can do this in two ways.

• Recursive
• Non-Recursive

Here we will see the non-recursive method. In general for reversing, we need to go the end(in case of string) and do the process. But in Linked list, no need of going to the end of the list. See below for details.

• Separate the first node from the list and make a new list with firs node. Now we have new lists. one list with out the first node and new list with first node.
• add each node from the old list to the new list, repeat this until first list reaches null. Now we will have new list with reverse order.

Lets see this with example. Below is the input list, we will do the reverse of this list.

Input List

Splitting list into two lists: First we need to split the list into two lists in such a way that, new list is having only one node which is head node of the given input and another list is given input list with out first node.  To point head node of the new list we need to take the new pointer newHead which points to head node.  and then do below steps as shown in the figure.




Before

Step1 : Move the head pointer to the next node
Step2 : Assign newHead  next pointer to NULL.

After



 head = head ->next;
 newHead->next = NULL:

Inserting node at starting of the new list: To append each node from given list to new list we need to follow the below steps in order. Should not change the order. And take one new pointer temp which points to the head node.


Before

Step1: Move the temp node pointer to the next node.
Step2: Change the head next pointer to the newHead node.
Step3: Move newHead to the head position
Step4: Move head to the temp node.


After



temp=head->next;
head->next = newHead;
newHead = head;
head = temp;

Repeat above steps 1-4 till temp reaches NULL. And the result list is given below.

reverse list

Here is the C program to delete the node from a linked list.