Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
1
Head Note: I have seen a post on the same problem posted previously on the forum.
http://forum.codecal...-recursion.html
But there are important aspects discussed in this tutorial that were not covered earlier:
1. This problem has many solutions including recursive, iterative using a new list,
iterative IN PLACE etc. The one mainly asked previously was using recursion in a constrained set of parameters passed to the main function i.e. you have to have list’s head and tail to pass to the function written. This means either you use a cyclic list or you iterate through the whole list to find the tail pointer.
2. I read on the post referenced that may be list reversal on a singly list in place iteratively is not possible. So I thought it would be worth posting such a solution.
This probably could be referred to as among the most common problems asked in programming interviews across the software development world if not the most common one.
People often make the fundamental mistake of thinking they only need to reverse the first and last element and they are done. So I am illustrating it with a clear example. We assume the list contains a single integer element as data and a next pointer for each Node of the list.
Original List: List Head -> 1 -> 2 -> 3 -> 4
Reversed List: List Head -> 4 -> 3 -> 2 -> 1
Note that every element in the list needs to be pointing to the one who was its previous in the original list. There can be many solutions, but I would like to discuss the most interesting one
Solution 1: Recursion
Think of the list as containing only two nodes. Then you just need to swap the Head and the tail and you are done. So if we treat this as our base case, we can recursively divide a larger list by reducing one element in every call until we reach the base case. Then with every return from previous recursive call we are adding one element to the inverted list. The above reference post can be used to see some details though there are slight variations with that.
Solution 2: Iteratively using a new list
There is a basic function usually written when creating a linked list called InsertAtHead. So we could simply create a new list, iterate through the old list while passing each node one by one to insert at head. This means head would be inserted first and tail would be inserted last. Effectively, we would obtained a reversed link list
i.e. New list is empty. First we are at 1, so we insert 1 in new list, and then we insert 2. Since it is insert at head so new list will look like 2 -> 1 after inserting 2. When we insert 3 it would be like 3 -> 2 -> 1 and so on. InsertAtHead function’s code will be included in the Solution 3.
Solution 3: Iterative In place – 3 pointer approach
Imagine you are traversing through the list and are somehow changing the direction of the links as you move along. At the end you will have a reversed list. However, how do you move ahead in a singly list if you are reversing each link as you move ahead? The answer is you keep one pointer to move ahead, one pointer to previous and one to current node. Hence it is called 3 pointers approach.
I have included the complete program so that any one not familiar with basic list can run it and verify the implementation. The delete function is not there to avoid adding more complexity though it should always be there in practice since we are allocating memory from the heap for each node.
#include <iostream>
using namespace std;
struct Node // A c++ struct is automatically used as a type.
{
int data;
Node *next;
};
Node * head; // The head of list
void insertAtHead(int val)
{
Node * newNode = new Node;
newNode->data = val;
newNode->next = NULL;
if(head != NULL)
{
newNode->next = head;
head = newNode;
}
else
head = newNode;
}
void printList(Node *cHead)
{
Node * temp = cHead;
while(temp != NULL)
{
cout << " " << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
Node * reverseListInPlace()
{
Node *curr, *prev, *next;
prev = NULL;
curr = head;
while(curr != NULL)
{
next = curr->next; // keep next saved to move forward in list
curr->next = prev; // reverse the current node's next ptr
prev = curr; // keep previous saved for use when reversing
curr = next; // move current forward in the list
}
return prev; // since it is the new head, curr would be null at this point
}
int main()
{
insertAtHead(5);
insertAtHead(4);
insertAtHead(3);
insertAtHead(2);
insertAtHead(1);
printList(head);
printList(reverseListInPlace());
return 0;
}
Edited by Alexander, 29 May 2011 - 05:07 PM.
Fixed encoding issues
Back to top
