JIYIK CN >

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

• Data item.
• The address of the next node.

class Node
{
    int data;
    Node *next;
};

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

Linked list reversal algorithm

Let headbe the first node of the linked list.

Iterative Algorithm

• Initialize 3 pointers - currset to head, prevand nextset to NULL.
• Traverse the linked list until you reach the last node, which is curr!= NULLand do the following:
  • Set nextto curr->next 个to nextmove to its next node.
  • prevReverses the direction of the current node by pointing it toward . Therefore, curr->nextset to prev.
  • Set prevto currto move it forward one position.
  • Set currto nextto move it forward one position.

Recursive Algorithm

• Split the list into two parts: the first node, the headnode, and the rest of the linked list.
• Call reverse(head->next), i.e., the remainder of the reverse linked list, and store the reverse linked list as rev.
• Append headto the end of the reverse-linked list rev.
• Points to head, that is, the tail of the reverse link list points toNULL

Reverse Linked List using Stack

• Initializes heada pointer to a linked list curr.
• Traverse the linked list and insert each node one by one.
• Update headto the last node in the linked list, which is the first node in the stack.
• Start popping nodes from the stack one by one and appending it to the end of the reverse linked list.
• Update the next pointer of the last node to NULL.

Linked list reversal diagram

• Initialize currto point to the head, that is, nodes 2and , prevand currthe data of is NULL.
• Sets nextto point to curr->nexta value equal to 4.
• Set curr->nextto prevto obtain 2a list of backward links headed by .
• Move prevto the node currwith data 2, and currmove to the node nextwith data .4
• Points nextto curr->nexta value equal to6
• Set curr->nextto prevto obtain a reverse linked list with 2and 4as reverse nodes and with 4as the head.
• Move prevto , that is, the node currwith data , and move to , that is, the node with data . 4currnext6
• Sets nextto point to curr->nexta value equal to 8.
• Set curr->nextto prevto obtain a reverse linked list with and 2as reverse nodes and headed by . 466
• Move prevto , that is, the node currwith data , and move to , that is, the node with data . 6currnext8
• Point nextto curr->next, that is NULL.
• Set curr->nextto prev, with 2, 4, 6and 8as reverse nodes and with 8as the head to obtain a reverse linked list.
• Move prevto curr, that is, 8the node with data , move currto NULL, and the algorithm terminates.

Implementation of linked list reversal

#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 situation

To reverse a complete linked list, we have to visit each node and then append it to the reversal list. Therefore, if a linked list has nnodes, the average case time complexity of traversal is about O(n). The time complexity is about O(n).

• Best Case

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

• Worst case scenario

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

Space complexity

The space complexity of this traversal algorithm is O(1), since no additional space is required except for the temporary pointers.