Can we reverse a linked list in less than O(n)?

Last Updated on June 22, 2022 by Ria Pathak

Introduction

Reversing a linked list is a very common operation that we need to perform while solving problems on linked list. So, if this operation is used a lot, let’s look at how fast it can be performed on linked lists of different types. And we will also find the answer to the question: Can we reverse a linked list in less than O(n) time ?

To answer this question, let’s discuss this operation on two most commonly used linked lists:

Singly linked list

In a singly linked list, we have the node as:

struct Node {
    int val;
    Node* next;
};

And the singly linked list would look something like:

Any method of reversing such a linked list will require at least one traversal of the linked list, visiting each node at least once. Then we can either use extra space or we can simply modify their pointers and reverse them. This can be implemented both recursively and iteratively in linear time.

So, there seems no way to do this work in less than O(n).

Doubly linked list

A node in a doubly linked list has a pointer to both next and previous nodes.

struct Node {
    int val;
    Node *next, *prev;
};

And the doubly linked list looks something like this:

In this doubly-linked list, one thing we can observe is that, if we traverse from the tail pointer towards the node pointed by the head pointer, then we would be traversing the linked list in reverse order.

So, for doubly-linked lists with a tail pointer, one thing that we can do so that it seems reversed is to swap head and tail pointers, which will take constant time. Now we have a linked list in which to traverse forward we would have to use the prev pointer and for backward traversal use the next pointer. Although the linked list would be reversed, it would create a lot of confusion while performing operations on such a linked list (as we need to treat prev as next and next as prev).

This is the only way where we can reverse a linked list in less than O(n) time.

In the above article, we discussed if we can reverse a linked list in less than O(n) time. Thinking about problems like these is good for strengthening your grip over LinkedList. I would highly recommend you to practice some problems on a linked list from PrepBytes Linked List.