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

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:

• 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

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.

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:

The reversed linked list would look like this:

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

==>Original Linked List
==>7 14 21 28 
==>Reversed Linked List
==>28 21 14 7

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.

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;
}
==>Original Linked List
==>7 14 21 28 
==>Reversed Linked List 
==>28 21 14 7 

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

• How to pass an array to a function in C++
• Intermediate C++ tutorial: Strings, maps, memory, and more
• 9 C++ data structures you need to know for your interview

Start a discussion

How do you approach reversing linked lists? Is there anything we missed that you'd like to learn about? Let us know in the comments below!