How to reverse a linked list in C++
In this shot, we will learn how to solve a very common interview problem based on linked lists.
In this problem, we are given a head of a linked list that contains some integers. We need to reverse the linked list so that the head now points to the last element, and all the pointers are reversed. Let’s look at the following visual to better understand the problem statement.
So, now that we are clear on what we need to do, we can think about how to approach a solution for this problem.
Solution
We will write an iterative solution to solve this problem.
This problem can also be solved with a recursive approach.
We will follow the steps below to solve the problem.
- Check if there is a 0 or 1 node in the linked list. If so, then return the head as it is.
- Initialize the
curr = head,prev = NULL, andtemp = NULLpointers. - We will use the three pointers above to swap the links of nodes.
- Then, we will run a loop until
currbecomesNULL. Inside the loop, we will perform the swapping, as mentioned in the steps below.- Point
temptocurr->next. - Set
curr->nexttoprev. (Link reversed) - Set
prev=currandcurr=tempfor the next iteration.
- Point
Let’s now look at the code and see how this will work.
node * reverse(node *head){if(head == NULL || head -> next == NULL)return head;node* current = head;node* prev = NULL;node* temp;while(current!= NULL){temp = current->next;current->next = prev;prev = current;current = temp;}return prev;}int main() {createLinkedList();cout << "The original linked list is: ";printLinkedList(head);node * reverseHead = reverse(head);cout << "\nThe reversed linked list is: ";printLinkedList(reverseHead);}
Explanation
- In line 1, we create a
reverse()function that accepts the head pointer of the linked list. (We will only learn to implement this function). - In line 2, we check for a zero or one node in the linked list. If so, we return that node itself.
- In line 8, we run a loop until we reach the last node.
- From lines 9 to 12, we perform the steps that we discussed in the logic above, where we will swap the pointers.
- Finally, in line 14, we return the new head of the linked list that actually points to the last node in the original linked list.
- In line 19, we call a
createLinkedList()function which will create a linked list that contains some integers. - In line 22, we print the original linked list.
- In line 24, we call the
reverse()function that we just created. - Finally, in line 27, we print the elements of the reversed linked list.
Check out my course Competitive Programming - Crack Your Coding Interview, C++ for additional help on how to prepare for coding interviews.
