Linked List Reversal

  1. Linked List Reversal Algorithm
  2. Linked List Reversal Illustration
  3. Linked List Reversal Implementation
  4. Linked List Reversal Algorithm Complexity

A linked list is a linear data structure. A node of the linked list consists of:

Reversing Text From a File in Pytho...
Reversing Text From a File in Python (Video 42)
  • A data item.
  • An address of the next node.
class Node
{
    int data;
    Node *next;
};

linked list

This article will introduce how to reverse a linked list given the pointer to the head node of the linked list.

Linked List Reversal Algorithm

Let the head be the first node of the linked list.

Iterative Algorithm

  • Initialize 3 pointers - curr as head, prev and next as NULL.
  • Traverse the linked list until you reach the last node i.e. curr != NULL and do the following:
    • Set next as curr->next to move next to its next node.
    • Reverse current node’s direction by pointing them toward prev. So, set curr->next as prev
    • Set prev as curr to move it one position ahead.
    • Set curr as next to move it one position ahead.

Recursive Algorithm

  • Divide the list into two parts: the first node, i.e., the head node, and the rest of the linked list.
  • Call reverse(head->next), i.e., reverse the rest of the linked list and store the reversed linked list as rev.
  • Append head to the end of the reversed linked list rev.

Reverse Linked List Using Stack

  • Initialize pointer curr to the head of the linked list.
  • Traverse the linked list and insert each node in the stack one by one.
  • Update head to the last node in the linked list i.e. the first node in the stack.
  • Start popping the nodes out of the stack one by one and append it to the end of reversed linked list.
  • Update the next pointer of the last node to NULL.

Linked List Reversal Illustration

linked list reversal

  • Initialize curr to point towards head i.e. node with data 2 and prev and curr as NULL.
  • Point next to curr->next with a value equal to 4.
  • Set curr->next as prev to get a reversed linked list with 2 as the head.
  • Move prev to curr i.e. node with data as 2 and curr to next i.e. node with data as 4.
  • Point next to curr->next with a value equal to 6.
  • Set curr->next as prev to get a reversed linked list with 2 and 4 as reversed nodes with 4 as the head.
  • Move prev to curr i.e. node with data as 4 and curr to next i.e. node with data as 6.
  • Point next to curr->next with a value equal to 8.
  • Set curr->next as prev to get a reversed linked list with 2, 4, and 6 as reversed nodes with 6 as the head.
  • Move prev to curr i.e. node with data as 6 and curr to next i.e. node with data as 8.
  • Point next to curr->next which is NULL.
  • Set curr->next as prev to get a reversed linked list with 2, 4, 6, and 8 as reversed nodes with 8 as the head.
  • Move prev to curr i.e. node with data as 8 and curr to NULL and the algorithm terminates.

Linked List Reversal Implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        this->data = x;
        this->next = NULL;
    }
};

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

Node* reverse(Node* head)
{

    Node* curr = head;
    Node *prev = NULL, *next = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}

Node* recursiveReverse(Node* head)
{
    if (head == NULL || head->next == NULL)
        return head;

    Node* rest = recursiveReverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

void reverseLL(Node** head)
{

    stack<Node*> s;
    Node* temp = *head;
    while (temp->next != NULL)
    {
        s.push(temp);
        temp = temp->next;
    }
    *head = temp;

    while (!s.empty())
    {
        temp->next = s.top();
        s.pop();
        temp = temp->next;
    }
    temp->next = NULL;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head -> next-> next = new Node(3);
    head -> next-> next-> next = new Node(4);
    head -> next-> next-> next-> next = new Node(5);
    head -> next-> next-> next-> next-> next = new Node(6);
    head = reverse(head);
    printList(head); cout << "\n";
    head = recursiveReverse(head);
    printList(head); cout << "\n";
    reverseLL(&head);
    printList(head); cout << "\n";
    return 0;
}

Linked List Reversal Algorithm Complexity

Time Complexity

  • Average Case

To reverse the complete linked list, we have to visit every node and then append it to reversed list. So, if a linked list has n nodes, the average-case time complexity of traversal is of the order of O(n). The time complexity is of the order of O(n).

  • Best Case

The best-case time complexity is O(n). It is the same as average-case time complexity.

  • Worst Case

The worst-case time complexity is O(n). It is the same as best-case time complexity.

Space Complexity

This traversal algorithm’s space complexity is O(1) as no extra space other than for temporary pointers is required.

Related Article - Data Structure

  • Circular Doubly Linked List
  • Circular Linked List
  • Doubly Linked List
  • Linked List Deletion
  • Related Article - Linked List

  • Circular Doubly Linked List
  • Circular Linked List
  • Doubly Linked List
  • Linked List Deletion