CODEWITHSUNDEEP
data-structureslinked-liststack
Ojas Kale
Ojas Kale

Reputation: 2159

Implementing Linked List reversal using Stack

I am trying to reverse a Linked List using Stack.

Node Reverse(Node head) {
    Stack<Node> x = new Stack<Node>();
    Node curr = new Node();
    curr= head;

    while (curr!=null){
        x.push(curr);
        curr=curr.next;

    }
    int i=0;
    while(!x.isEmpty()){
        if (i=0){
            head=x.pop();
            i++;
        }
        else{
            Node temp = new Node();
            temp = x.pop();
        }
    }
}

Here's my code. I am stuck in the while loop. Could you please help.?

Upvotes: 0

Views: 63

Answers (4)

Konrad Rudolph
Konrad Rudolph

Reputation: 545865

At the core of programming is abstraction. You can make your code substantially simpler (and, hence, easier) by abstracting the linked list behind an interface. Once you’ve done it, the reversal via a stack is as simple as this:

void Reverse(LinkedList<T> list) {
    Stack<T> stack = new Stack<T>();

    while (! list.IsEmpty())
        stack.Push(list.RemoveFront());

    while (! stack.IsEmpty())
        list.AppendBack(stack.Pop());
}

That is, think of your list as a unit with its own interface, rather than passing around nodes in client code. Nodes are only touched inside the LinkedList class.

Upvotes: 0

blazs
blazs

Reputation: 4845

There's at least three problems with the code:

  • as mentioned, i=0 should be i==0 in condition of the if statement;
  • when you pop a non-head node off the stack, you're not doing any linking; you should probably say something like prev.next = curr where curr and prev are defined in an obvious way;
  • the function is defined as returning a (reference to) Node; the code you gave doesn't return anything.

Also, I would suggest using the following iterative approach that's simpler and more efficient.

/* ... */
typedef struct node_t_ node_t;

struct node_t_ {
    node_t *next;
    int v;
};
/* ... */
node_t *reverse(node_t *head) {
    node_t *curr, *prev, *temp;

    prev = NULL;
    curr = head;
    while (curr != NULL) {
        temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }

    return prev;
}

I wrote the code in C; you should have no problems converting it to Java.

Upvotes: 0

Ojas Kale
Ojas Kale

Reputation: 2159

Node Reverse(Node head) {
    Stack<Node> x = new Stack<Node>();
    Node curr = new Node();
    curr= head;

    while (curr!=null){
        x.push(curr);
        curr=curr.next;

    }




            Node temp = new Node();
            temp=x.pop();
            head=temp;
            x.pop();
            while(!x.isEmpty()){
            temp = x.pop();
                if (x.peek()!=null){
            temp.next=x.peek();
            }
                else{
                    temp.next=null;
                }
            x.pop();
            temp=temp.next;    

            }

    return head;
}

I have taken lead till here. but still unable to deal with empty stack exception.

This is not a final solution.

Upvotes: 0

FallAndLearn
FallAndLearn

Reputation: 4135

Your code below will run in a while loop infinitely.

if (i=0){
            head=x.pop();
            i++;
        }

You should change i=0 to i==0

if (i==0){
                head=x.pop();
                i++;
            }

Upvotes: 1

Related Questions