How do I reverse a linked list using recursion?

You should reverse a linked list by modifying the node connections. Start from a given pointer to the list’s head node. This should be accomplished using a recursive approach.

Home/Blog/Programming/Tutorial: How to reverse a linked list in C++

Tutorial: How to reverse a linked list in C++

Erica Vartanian

Nov 20, 2023

5 min read

content

Linked lists Problem description: Reversing a linked list Solution 1: Reverse a linked list using iteration Solution 2: Reverse a linked list using recursion Wrapping up and next steps Continue learning about C++

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Knowing how to work with the C++ programming language makes you a competitive candidate for various roles. As you break into new roles, you’ll advance through interviews that test your understanding of computer science fundamentals such as data structures and algorithms. A linked list is just one of many C++ data structures you need to know for interviews. One popular interview question is reversing a linked list.

Today, we’ll cover a tutorial on reversing singly linked lists in C++. We’ll demonstrate an iterative and recursive solution to this problem.

We’ll cover:

Get hand-on with C++ today.

Ace the C++ Coding Interview

C++ is a general purpose, low-level, objected-oriented language. C++ is widely used in various fields such as game development, virtual reality, automotive and avionics, financial systems, medical equipment, and even the space industry. The compatibility of C++ makes it a perfect language for developing operating systems, game engines, desktop and mobile applications, and high-performance computing systems. This Skill Path will take you through all that you need to know to crack your C++ interviews with confidence. You’ll cover everything from data structures to Object-oriented design. You will also get to know the essential patterns behind popular coding interview questions. By the time you’re done with this Skill Path, you’ll be ready to ace the interview of any company.

221hrs

Beginner

168 Challenges

250 Quizzes

Linked lists#

Linked lists are linear data structures connecting nodes in a sequence. Each node has two components: 1.) A data element and 2.) A pointer containing a memory address to the next node in the list.

diagram linked list

In the case of a singly linked list, nodes only store one pointer to the next node in the sequence. A node in a doubly linked list, on the other hand, stores two pointers: one to the next node, and one to the previous node in the sequence. A singly linked list is uni-directional while a doubly linked list is bi-directional. In the case of a singly linked list, the tail node’s pointer is null.

Some terms associated with linked lists are:

Node: The object in the list, with two components: a piece of data (element) and a pointer.
Next: The next node in a sequence, respective to a given list node
Head: The first node in a linked list
Tail: The last node in a linked list is called the tail.
Head pointer: The memory address contained by the head node referencing the first node in the list

Linked lists may be the second most used data structure, behind arrays. Linked lists are great for quickly adding and deleting nodes. They can be used to implement stacks and queues, as well as other abstract data types. Linked lists are often used to maintain directories of names, or for dynamic memory allocation.

Problem description: Reversing a linked list#

We’re provided the pointer or reference to the head node of a singly linked list. We must sequence the list in reverse order and return the pointer to the head of the reversed linked list. The head of the original linked list becomes the tail of the reversed linked list, and the tail of the original linked list becomes the head of the reversed linked list.

For example, provided the given linked list: linked list diagram

The reversed linked list would look like this: reversed link list diagram

Solution 1: Reverse a linked list using iteration#

If the linked list has two or more elements, we can use three pointers to implement an iterative solution. We use a function to reverse the linked list. Passing the head pointer as the sole argument, the function will return the head of the reversed list.

We’ll define three nodes: current (with reference to the head node), and temp and prev (with null pointers). Using a while loop, we traverse the linked list until the next pointer does not yield null.

In the iterative process, we’ll perform these operations:

temp = current->next;
- Assigns temp node to the current node’s next node
current->next = prev;
- Assigns current node to the previous node’s next node
prev = current;
- Increments previous node to current node
current = temp;
- Increments current node to temp node

We then return the reversed list’s head node.

#include<bits/stdc++.h>
 
using namespace std;
 
struct node {
    int data;
    struct node *next;
};
 
// We construct a linked list and use this function to push elements to the list 
void push(struct node **head_ref, int data) {
    struct node *node;
    node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->next = (*head_ref);
    (*head_ref) = node;
}
 
// Function to reverse the list
void reverse(struct node **head_ref) {
    struct node *temp = NULL;
    struct node *prev = NULL;
    struct node *current = (*head_ref);
    while(current != NULL) {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    (*head_ref) = prev;
}
 
// Checking our program 
void printnodes(struct node *head) {
    while(head != NULL) {
        cout<<head->data<<" ";
        head = head->next;
    }
}
 
// Driver function
int main() {
    struct node *head = NULL;
    push(&head, 28);
    push(&head, 21);
    push(&head, 14);
    push(&head, 7);
    cout << "Original Linked List" << endl;
    printnodes(head);
    reverse(&head);
    cout << endl;
    cout << "Reversed Linked List"<<endl;
    printnodes(head);
    return 0;
}

Get hands-on with C++ today.

Ace the C++ Coding Interview

221hrs

Beginner

168 Challenges

250 Quizzes

Solution 2: Reverse a linked list using recursion#

The recursive solution uses a stack. Each recursive call requires your compiler to allocate stack memory. Since recursive implementation can run out of memory, the recursive solution isn’t the best approach when working with very large linked lists.

To return the head of the new list, we recursively visit each node in the given linked list until we reach the last node. This last node then serves as the new head of the list. On the return path, each node appends itself to the end of the partial reversed list.

#include<bits/stdc++.h>
using namespace std;
 
 
struct Node {
    int data;
    struct Node* next;
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
struct LinkedList {
    Node* head;
    LinkedList()
    {
        head = NULL;
    }
 
    Node* reverse(Node* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        // Recursive call
        Node* rest = reverse(head->next);
        head->next->next = head;
        
        head->next = NULL;
 
        return rest;
    }
 
    void print()
    {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
 
    void push(int data)
    {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
 
int main()
{
    LinkedList ll;
    ll.push(28);
    ll.push(21);
    ll.push(14);
    ll.push(7);
 
    cout << "Original Linked List\n";
    ll.print();
 
    ll.head = ll.reverse(ll.head);
 
    cout << "\nReversed Linked List \n";
    ll.print();
    return 0;
}

Wrapping up and next steps#

Now you know how to reverse a linked list! This is a common question in C++ coding interviews. Before going to a coding interview, you’ll want to be comfortable with as many C++ data structures as possible.

To help you learn C++, check out our Ace the C++ Coding Interview learning path. This interactive learning path helps you prepare for C++ interviews with several modules and quizzes, including content covering several other operations on data structures.

Happy learning!

Continue learning about C++#

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments