Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
link
iterativesolution
communitycreator

How to reverse a linked list in C++

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.

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

}
Reverse a linked list in C++

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.

RELATED TAGS

c++
link
iterativesolution
communitycreator
RELATED COURSES

View all Courses

Keep Exploring