Reverse linked list is the one of the most common question in C/C++ interview question. Generally we can do this in two ways.
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.
Step1 : Move the head pointer to the next node
Step2 : Assign newHead next pointer to 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.
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.
Repeat above steps 1-4 till temp reaches NULL. And the result list is given below.
Here is the C program to delete the node from a linked list.
- Recursive
- Non-Recursive
- 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.
Input List |
Before |
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 |
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.
No comments:
Post a Comment