In all my years as a software developer, reversing a singly linked list is not something I’ve had to do. But it is a commonly asked question in interviews for programming positions. Of course the easy solution to the problem is to place items in a Standard C++ collection, like a vector, then apply the
reverse() function to the collection.
For those of you who want or have to roll your own solution, here is an example of a simple list structure and a reverse list function.
Linked List Node
All the code for linked list and test application in this example is defined in a single file rlist.cpp. The nodes to be stored in the linked list will simply contain and integer value and a pointer to the next node in the list.
The linked list to be created will be of the most basic type. There will be a head pointer and the last node will have the
m_next member variable set to
createNode() function gets the integer to be storied then creates a
node_t item to contain it and sets the next pointer to NULL.
Add a Node
New nodes will be placed at the end of the linked list. To find the end, iterate through the list items until an item with
m_next set to
NULL is encountered. Then set this item’s
m_next to the new node pointer.
Print the List
To check the items on the queue the
printList() function iterates through the list printing the value at each node that is encountered. So we can see everything easily, all the values of a list will be displayed on one line.
Reverse the List
Now the function you have been waiting for. The trick to this algorithm is you need 3 node_t pointers to accomplish the reversal.
next- Tracks the pointer to the next item in the list.
head- Initially contains the original head of the list but will then be set to the pointer to the next item in the list until the
NULLpointer is encountered.
cursor- Initially is set to
NULLbut then tracks the new head of the list. At the end of the list,
NULLand the value of
cursoris returned to the caller.
The reversal step occurs when
head->m_next is set to the value contained in cursor which always contains the pointer to the previous item in the list. When the function reaches the end of the list the new head pointer is returned in cursor.
To test the reverse link list algorithm, we’ll add numbers to the linked list from 0 – 19, in order, then call
reverseList() to reorder the numbers.
Build and Run
You can get the source code for the project from Github – https://github.com/vichargrave/rlist. To build the test application just cd into the
rlist directory then run make.
When you run the program you will get this output: