What's wrong with my code in java with stack? wrong result


  • 0
    C

    public class Solution {
    public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<ListNode>();
    ListNode node = head;

        if(node == null){
            return null;
        }
        
        while(node.next != null){
            stack.push(node.next);
            node = node.next;
        }
        
        node = head;
        while(!stack.empty()){
            node.next = stack.pop();
            node = node.next;
        }
        node.next = null;
        return head;
    }
    

    }


  • 0
    C

    When you reverse a list the tail should become the new head. In your case you revere everything except the head. In the above code you use the same head and connect the reversed list (without the head) to the original head.
    I made the C++ version of reversal using stack hope you can convert it to Java and see for yourself.

    ListNode* reverseList(ListNode* head) {
    stack<ListNode*> stk;
    ListNode* node= head;
    
    while (node != NULL) { // push to stack (including head)
    	stk.push(node);
    	node = node->next;
    }
    
    head = new ListNode(0); // dummy head to attach reversed list
    node = head;
    while (!stk.empty()) {
    	node->next = stk.top();
    	stk.pop();
    	node= node->next;
    }
    node->next = NULL;
    return head->next;
    
    }
    

  • 0
    Z

    node = head; was wrong, should be node = stack.pop(); head= node;.


  • 0
    C

    Do you notice that the return is head->next ? i.e. skipping the dummy head.


  • 0
    C

    Oops. I had no ideal that the head actually contains value. I thought it only works as a pointer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.