CODEWITHSUNDEEP
javaliststackreverse
Riddhesh Sanghvi
Riddhesh Sanghvi

Reputation: 1222

Is reversing a linked list better by using stacks?

I was reversing a singly linked list using the following code:

Node prevNode = null;
Node currNode = head;
while (currNode != null) {
    Node next = currNode.next;
    currNode.next = prevNode;
    prevNode = currNode;
    currNode = next;
}
head = prevNode;

Then when I was going through some material about stacks it suggested that reversing any list is best done by using a stack.

It is for sure very easy to visualize that we indeed pop out the elements and push them into a new stack and in the end it is essentially reversed. But which of the two methods is better or would take lesser time?

Upvotes: 1

Views: 544

Answers (2)

user5034652
user5034652

Reputation:

By reversing I guess it means making the links between two elements opposite to what it previously was i.e. if it was 1->2->3->4 then it is now 1<-2<-3<-4.

The best way to do it is by breaking this list into two parts namely current and rest, it is a recursive approach.

Time Complexity: O(n), Space Complexity: O(1)

1->2->3->4

1->2->3<-4 (4 being the rest)

1->2<-3<-4

1<-2<-3<-4

You can find the details of this approach here: enter link description here

Upvotes: 4

Thomas Mathew
Thomas Mathew

Reputation: 429

An in-place reversing is always better than using a stack, because we are not using any additional space. However, for an immutable list, the only option to reverse is to use to stack too.

Upvotes: 2

Related Questions