Reversing a linked list is a simple programming problem, which is often an 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 linked 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
If you are interested in other linked list related code I have a post about picking the 5th from last element from a singly linked list, and one on selecting random numbers from a stream or linked list. Both of these are based on programming interview questions.
This is the most elegant way I’ve seen so far !
Thanks
+1
de way u explained s simple and understandable.
You are awesome.
:-)))))
Sorry i do not understand this part, how does this select each item and put them into the newList? this while loop will run till current==NULL? right?
while (current)
{
Node* next = current->next;
current->next = newList;
newList = current;
current = next;
}
Hi yj, this code moves the nodes from one list to another by changing the next pointers. The easiest way to understand it is to get a piece of paper and work through the loop for the 1,2,3,4,5 example above.
Yes it stops when current==NULL.
hey, i got it thanks.. i was thinking of another way which may be easier. It works when you have both the prev and next pointer for each Node object. So to reverse the order, just interchange the next and prev pointers for each Node obj..Anyway thanks for sharing..Cheers
It seems you are writing C in C++ grammar.
I never see this assign statement before Node* next = current->next, but I’ve seen like this Node* temp-next = current->next;
Can you explain little bit?
Hi everyone I have question I liked this code but there is a some lines that I did not get what it do and when I tried to delete this line from the compiler it did not compile so can you explain to me what this do
Node(int value) : value(value), next(NULL) {}
I studied that ( : ) use for inheritance between tow class sorry I did not get it what is value(value) and next(NULL)
And then in the next lines the node val and the pointer initialized
public:
int value;
Node* next;
};
so what is this class please explain.