Trusted answers to developer questions

Harsh Jain

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.

Problem statement visualization

So, now that we are clear on what we need to do, we can think about how to approach a solution for this problem.

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`

, and`temp = NULL`

pointers. - We will use the three pointers above to swap the links of nodes.
- Then, we will run a loop until
`curr`

becomes`NULL`

. Inside the loop, we will perform the swapping, as mentioned in the steps below.- Point
`temp`

to`curr->next`

. - Set
`curr->next`

to`prev`

. (Link reversed) - Set
`prev`

=`curr`

and`curr`

=`temp`

for 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); }

Reverse a linked list in C++

- 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.

RELATED TAGS

c++

link

iterativesolution

communitycreator

CONTRIBUTOR

Harsh Jain

RELATED COURSES

View all Courses

Keep Exploring

Related Courses