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

5 min read
Erica Vartanian
editor-page-cover

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 hands-on with C++ today.

Try one of our 300+ courses and learning paths: Ace the C++ Coding Interview.

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

O(N) is the time complexity of this solution since we iterate through each element at least once. O(1) is the space complexity because no extra memory was needed for the solution.

Get hands-on with C++ today.

Try one of our 300+ courses and learning paths: Ace the C++ Coding Interview.


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

The space complexity of this solution is O(N) since we create a recursive stack for each recursive function call. O(N) is the time complexity of this solution, since we iterate through each element at least once.

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


WRITTEN BYErica Vartanian

Join a community of 500,000 monthly readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.