Reverse a linked list - C++ source code
Reversing a linked list is a simple programming problem, which is often a interview question. In this case I’m referring to a singly linked list. I’ll provide the C++ solution and the C++ test code.
One of the easiest ways to reverse the list is to create a new head pointer, iterate through the list removing each item in turn and then inserting them at the beginning of the new list.
Here is the definition of my linked list node and the code to reverse the list.
class Node
{
public:
Node(int value) : value(value), next(NULL) {}
public:
int value;
Node* next;
};
Node* reverseList(Node* head)
{
Node* newList = NULL;
Node* current = head;
while (current)
{
Node* next = current->next;
current->next = newList;
newList = current;
current = next;
}
return newList;
}
Below is the code I used to test this. This is what it does:
- It creates a simple linked list.
- Prints it out - output should be ‘12345′.
- Reverses it.
- Prints it out - output should be ‘54321′.
- Reverses it again.
- Prints it - output should be ‘12345′.
- Deletes the list.
void listTests()
{
Node* one = new Node(1);
Node* two = new Node(2);
Node* three = new Node(3);
Node* four = new Node(4);
Node* five = new Node(5);
one->next = two;
two->next = three;
three->next = four;
four->next = five;
Node* head = one;
printList(head);
head = reverseList(head);
printList(head);
head = reverseList(head);
printList(head);
// cleanup memory
Node* current = head;
while (current)
{
Node* next = current->next;
delete current;
current = next;
}
}
void printList(Node* head)
{
Node* current = head;
while (current)
{
cout << current->value;
current = current->next;
}
cout << endl;
}
This should be the output:
12345 54321 12345
Tags: C++, code, interview question, source, source code
