Write a Program to reverse a Linked list

There are many ways to reverse a linked list, but here we’ll discuss 2 methods to do so.

1.  Iterative Method:

This is the most simple method to reverse a linked list. This is the first thought that would come to anybody’s mind if he/she thinks on how to reverse a linked list. Let’s take a simple linked list:

Now what we are gonna do is to make the last node as head and first as tail, so simply we will reverse the links in opposite direction and make head as last member of linked list, so that the linked list becomes reverse.

Technically: Iterate through the linked list. In loop, change next to prev, prev to current and current to next.

Now let’s implement this in program:

Reverse a Linked List using Iterative method:

#include<iostream>
using namespace std;

/* Link list node */
struct node
{
    int data;
    struct node* next;
};

/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head_ref = prev;
}

/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node = new node();

    /* put in the data  */
    new_node->data  = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}

/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while(temp != NULL)
    {
        cout<<temp->data<<endl;
        temp = temp->next;
    }
}

int main()
{
    /* Start with the empty list */
    struct node* head = NULL;

    push(&head, 12);
    push(&head, 4);
    push(&head, 15);
    push(&head, 9);

    cout<<"n Original Linked list n";
    printList(head);
    reverse(&head);

    cout<<"n Reversed Linked list n";
    printList(head);

    return 0;
}

Sample Output:

Original Linked list
9
15
4
12

Reversed Linked list
12
4
15
9

Time Complexity: O(n)
Space Complexity: O(1)

2.  Using Recursion:

• Divide the list in two parts – first node and rest of the linked list.
• Call reverse for the rest of the linked list.
• Link rest to first.
• Fix head pointer

Reverse a linked list using recursion:

void recursiveReverse(struct node** head_ref)
{
    struct node* first;
    struct node* rest;

    /* empty list */
    if (*head_ref == NULL)
       return;

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref;
    rest  = first->next;

    /* List has only one node */
    if (rest == NULL)
       return;

    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first;

    /* tricky step -- see the diagram */
    first->next  = NULL;

    /* fix the head pointer */
    *head_ref = rest;
}

Time Complexity: O(n)
Space Complexity: O(1)

Just use this function in the same program and you will get the output.

For any query comment below.