To reverse a linked list, you need to update the links between the nodes. The basic idea is to traverse the list while changing the next pointers to reverse the links.

Here is the C++ code to reverse a linked list:

1#include <iostream>
2using namespace std;
3
4// Function to reverse a linked list
5void reverseList(Node* &head) {
6    Node* current = head;
7    Node* prev = nullptr;
8    Node* next = nullptr;
9
10    while (current != nullptr) {
11        next = current->next;
12        current->next = prev;
13        prev = current;
14        current = next;
15    }
16
17    head = prev;
18}
19
20int main() {
21    // Linked list nodes
22    Node* head = new Node(1);
23    Node* second = new Node(2);
24    Node* third = new Node(3);
25    Node* fourth = new Node(4);
26
27    // Connect nodes
28    head->next = second;
29    second->next = third;
30    third->next = fourth;
31
32    cout << "Original List: ";
33    printList(head);
34
35    // Reverse the list
36    reverseList(head);
37
38    cout << "Reversed List: ";
39    printList(head);
40
41    return 0;
42}

Let's go through the code step by step:

• The function reverseList takes a reference to the head of the linked list as a parameter.
• Inside the function, we define three pointers: current, prev, and next.
• We initialize current with the head of the linked list and prev and next with nullptr.
• We then iterate through the list using a while loop until current becomes nullptr.
• Inside the loop, we first store the next node in the next pointer.
• Then, we update the next pointer of the current node to point to the previous node.
• After that, we update prev to be the current node and current to be the next node.
• Once the loop ends, we update the head of the linked list to be the last node we reached (previously prev).
• Finally, we print the original and reversed lists using the printList function.

The time complexity of this algorithm is O(n) as we need to traverse the entire list once to reverse it.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Function to reverse a linked list

void reverseList(Node* &head) {

    Node* current = head;

    Node* prev = nullptr;

    Node* next = nullptr;

​

    while (current != nullptr) {

        next = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

​

    head = prev;

}

​

int main() {

    // Linked list nodes

    Node* head = new Node(1);

    Node* second = new Node(2);

    Node* third = new Node(3);

    Node* fourth = new Node(4);

​

    // Connect nodes

    head->next = second;

    second->next = third;