Related Tags

reverse
node

When given a singly linked list with an additional head pointer, implementing​ the reverse() method does the following:

• All the links start pointing in the opposite direction.
• The head starts pointing to the last element of the list.

## Algorithm

Let’s have a look at an iterative approach of how to reverse a given linked list:

• Initialize the following node pointers:
• previous: Initially pointing at None, this node pointer points to the previous element so that the next link of the node can be reversed using it. This node pointer is then updated to the node next to it (i.e., current).

• current: Initially pointing to head, the node being pointed to by this node pointer gets its next variable set to the previous item in the list. This node pointer is then updated to the node next to it (i.e., following).

• following: Initially pointing to the second node, this node pointer​ is used so that the current pointer may move one step ahead in each iteration.

## Implementation

The code tabs, below, implement the algorithm above.

#include <iostream>
using namespace std;

// Node implementation
struct Node {

int data;
struct Node* next;

//constructor
Node(int data)
{
this->data = data;
this->next = NULL;
}
};

{
}

// Function to reverse the linked list
void reverse()
{
// Initialize current, previous and
// following pointers
Node *previous = NULL;
Node* following = current->next;

while (current != NULL) {
current->next = previous;

// move previous one step ahead
previous = current;

// move current one step ahead
current = following;

// move following to the next element if it exists
if (following)
following = following->next;
}
}

// Print list
void print()
{

while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}

cout << endl;
}

// function to insert element into the linked list
void insert(int data)
{
Node* temp = new Node(data);
}
};

int main()
{
ll.insert(4);
ll.insert(3);
ll.insert(2);
ll.insert(1);

cout << "Original linked list" << endl;
ll.print();

ll.reverse();

cout << "Reversed Linked list" << endl;
ll.print();

return 0;
}


RELATED TAGS