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.

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.

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

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.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)