Skip to content
How to Reverse a Linked List

Reverse a Linked List

Yes, we are doing it today. The all-time famous interview question, Do you know how to reverse a Linked List? Well turns out, it isn’t that difficult and it’s all about logic and pointers, okay let’s get started.

Alright, I already wrote a post explaining the basic operations and structure of a Linked List. If you want to revise, have a look at – Linked List

Example

This a normal Linked List, where each element in the list points to the next item.

[1] => [2] => [3] => [4] => [5]

So, in order to reverse a linked list, we need to do something like this,

[1] <= [2] <= [3] <= [4] <= [5]

Solution Approach

Before we move on, let’s see the constraints/conditions

  • Each item/node can point to only one node at a time
  • The [HEAD] pointer usually points to the first node
  • Space should be constant
  • We will do this in one iteration

Pseudocode

  • Start iterating through the linked list
  • We use three pointers PREV, CURRENT, and NEXT
  • CURRENT and NEXT keep iterating and
  • PREV stays at the previous node and
  • We point the current Node’s next to PREV
[prev]  <=  [current]    [next]
  • After this PREV = CURRENT
  • Now, we make CURRENT = NEXT, so that we move to the next node
  • And again NEXT => CURRENT => NEXT
  • Now again point CURRENT node’s next to prev

I know this can be overwhelming and I made an info-graphic to make things simple you can follow this or code below to understand it easily.

Linked List
Reversing Linked List
Reverse a Linked List

Code

Reverse a Linked List C++

#include <iostream>
using namespace std;

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

class LinkedList
{
private:
    Node *first;

public:
    LinkedList() { first = NULL; }
    LinkedList(int A[], int n);
    //destructor
    ~LinkedList();
    void Display();
    void Reverse();
};

void LinkedList::Reverse()
{
    Node *current=first;
    Node *prev=NULL, *next=NULL;
    while (current!=NULL)
    {
        next=current->next;
        current->next=prev;
        prev=current;
        current=next;
    }
    first=prev;
}

LinkedList::LinkedList(int A[], int n)
{
    Node *last, *t;
    int i = 0;
    first = new Node;
    first->data = A[0];
    first->next = NULL;
    last = first;

    for (i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

LinkedList::~LinkedList()
{
    Node *p = first;
    while (first)
    {
        first = first->next;
        delete p;
        p = first;
    }
}

void LinkedList::Display()
{
    Node *p = first;
    while (p)
    {
        cout << p->data <<" " ;
        p = p->next;
    }
    cout << endl;
}

int main()
{
    // reversing a linked list
    int A[] = {11, 22, 33, 44, 55};
    LinkedList l(A, 5);
    l.Display();
    l.Reverse();
    l.Display();
    l.~LinkedList();
    return 0;
}

Conclusion

The best way to understand this would be to perform a dry run using a pen and paper, trust me once you know what’s happening at each step you’ll grasp the logic easily. This post is part of my #30DaysChallenge to write a blog post every day on what I learn. I hope you found this helpful ~ Thank You, Abhiram Reddy.

Tags: