Reverse a Linked List with time complexity O(1)

Question

Is it possible to reverse a Linked List with time complexity of O(1).

Answer 1

Yes, it is possible in O(1) to reverse:

• A doubly-linked list.
• A singly-linked list. (With a bit of twisting of the definition.)

---

How to reverse a doubly-linked list in O(1)

It is a very old trick, amazing in its simplicity.

Just keep a flag within the linked list class, which specifies whether the list is currently considering itself as "normal" or "reversed".

When the list is considering itself as "normal", it works the way you know.

When the list is considering itself as reversed, then it swaps the meaning of head and tail, and for each node in the list it swaps the meaning of previous and next.

So, all you need to do in order to reverse the list is to flip that flag.

The time complexity of flipping a flag is O(1), so, there you go.

Of course, for that to work, your linked list must fully encapsulate itself. You cannot have some leaky abstraction here. (Then again, you should not have any leaky abstractions anywhere. https://en.wikipedia.org/wiki/Leaky_abstraction)

---

One easy way to swap the meaning of head and tail without introducing a huge number of additional if statements (since linked list logic already contains a large number of those) is as follows:

1. Store the head and tail in an array anchor[0..1]
2. Represent your reversed flag as an integer which can be either 0 or 1.
3. Always use anchor[reversed] as the head.
4. Always use anchor[1 - reversed] as the tail.

• When the reversed flag is 0:
  • anchor[reversed] is anchor[0]
  • anchor[1 - reversed] is anchor[1].
• When the reversed flag is 1:
  • anchor[reversed] is anchor[1]
  • anchor[1 - reversed] is anchor[0].

So, flipping the reversed flag swaps the meaning of head and tail without the need of any additional if statements. Then you repeat the same trick with the prev and next pointers in each node of the linked list: replace those two pointers with an array link[0..1], and define prev as link[reversed] and next as link[1 - reversed].

---

How to reverse a singly-linked list in O(1)

Here we will need to bend a little bit the definition of a singly-linked list. We are going to say that a singly-linked list is a list which contains only one pointer per node, without imposing any other restrictions.

And what we are actually going to do is that we are going to implement a doubly-linked list using one pointer per node.

Yes, you heard that right, it is possible to have a doubly linked list with just a single pointer per node.

The trick is to bitwise - combine the prev and next pointers in each node using XOR into a single pointer called prevXorNext. This trick is based on the realization that whenever you arrive at a linked list node, you arrived there from another node, and you already know the pointer to that node, so this is a piece of information that you can make use of.

• When traversing forward:
  • By XORing the prevXorNext pointer of the current node with the pointer that you already have from the previous node, you get the pointer to the next node.
• When traversing backward:
  • By XORing the prevXorNext pointer of the current node with the pointer that you already have from the next node, you get the pointer to the previous node.

This is deep hacking, but it is also hacking at its best.

Of course keep in mind that this trick, as described, will not work in garbage collected languages, where it is impossible to manipulate the bits of pointers. To make this trick work in garbage-collected languages you would have to store the nodes in an array, so that instead of pointers you have integers, acting as array indexes, so that you can manipulate the bits of the integers.

Answer 2

If you are asking about Singly linked list then you cannot reverse it in less than O(n).

But a Doubly linked list can be reversed in O(1) time.

Reference : https://www.geeksforgeeks.org/can-we-reverse-a-linked-list-in-less-than-on/#:~:text=A%20doubly%20linked%20list%20with,may%20not%20be%20considered%20valid.