Reversing a singly linked list

Idea to reverse a singly linked list is a below.

a) If there is just a one node in a singly linked list, we return it as it is as there aren’t any links to be reversed.
b) If there are more than one nodes in a singly linked list, we do the following..

  • Start with the Head node and use two additional nodes current_node and next_to_current.
    current_node stores the address of Head node.
    next_to_current stores the address of Head’s next node.

1_Reverse_Singly_Linked_List

  • Point Head’s next to Null.
  • Store the address of the node next to next_to_current into a temp node before reversing the link of next_to_current.
  • Point next_to_current to current thus reversing the links between them.
  • current takes the place of next_to_current & next_to_current takes place of temp as the reversal of the links happen between every pair of adjacent nodes.

Time Complexity : O ( N ), where N is the number of nodes in the linked list.
Space Complexity : O ( N ), where N is the number of nodes in the linked list.



C++ program to reverse a singly linked list.

#include<iostream>

using namespace std;

class Node {

    public:
    int data;
    Node * next;
    Node (int arg_data) : data (arg_data), next (nullptr)
    {}
};

class SingleLinkedList {

    public:

    SingleLinkedList()
    {}

    void Display (Node * head) {

        Node * current = head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
    }

    Node * Reverse (Node * head) {

        // If head is null or only head (i.e single node), return head.
        if (head == nullptr || head->next == nullptr)
            return head;

        Node * current = head;
        Node * next_to_current = head->next;
        head->next = nullptr;

        while (next_to_current != nullptr) {

            Node * temp = next_to_current->next;
            next_to_current->next = current;

            current = next_to_current;
            next_to_current = temp;
        }
        return current;
    }

    // Free the linked list
    void Free (Node *head) {
        while (head != nullptr) {
            Node * temp = head->next;
            head->next = nullptr;
            delete head;
            head = temp;
        }
    }
};

int main() {

   Node * head = new Node(2);
   Node * node_3 = new Node(3);
   Node * node_5 = new Node(5);
   Node * node_7 = new Node(7);
   Node * node_11 = new Node(11);
   Node * node_13 = new Node(13);

   head->next = node_3;
   node_3->next = node_5;
   node_5->next = node_7;
   node_7->next = node_11;
   node_11->next = node_13;

   SingleLinkedList s;

   cout <<"\nSingle linked list : " << endl;
   s.Display(head);
   cout <<"\nReversing the single linked list : " << endl;
   head = s.Reverse(head);
   s.Display(head);
   cout <<"\nFreeing the single linked list." << endl;
   s.Free(head);

   return 0;
}

Output

Single linked list : 
2 3 5 7 11 13 
Reversing the single linked list : 
13 11 7 5 3 2 
Freeing the single linked list.


© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The trouble with programmers is that you can never tell what a programmer is doing until it's too late. - Seymour Cray"