java: Memory Limit Exceeded?

Question

I write a code by java in leetCode, this is the link: https://leetcode.com/problems/reverse-linked-list/description/

it shows "Memory Limit Exceeded", can anyone explain why?(you can just paste my code to the above link to see the error)

My code is as follows:

  public static class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
   }


public ListNode reverseList(ListNode head) {
    if(head ==null)
        return head;
    if(head.next ==null){
    return head;
    }
    Stack<ListNode> mStack =new Stack<>();
    while(head!=null){
        mStack.push(head);
        head = head.next;

    }
    ListNode mNode = new ListNode(0);
    ListNode result =mNode;
    while(!mStack.empty()){
       ListNode temp =  mStack.pop();;
        mNode.next = temp;
        mNode = mNode.next;

    }
    return result.next;

}

Answer 1

The problem is that, suppose the input is 1->2->3. Then what you will return is 3->2->1->2->1->2..... This circular linked list will cause Memory Limit Exceeded when calling toString method. To solve this, just set the next of original head to null.

Answer 2

This is because they expect you to do it in constant space complexity. A simple recursive solution would be :

class Solution {



public ListNode reverseList(ListNode head) {
    if (head==null){
        return head;
    }
    return reverseList(head,null);
}

public ListNode reverseList(ListNode current,ListNode prev){
    if (current.next==null){
        // we have reached the last node. This will be the new head
        current.next = prev;
        return current;
    }
    ListNode head = reverseList(current.next,current);
    current.next=prev;
    return head;

}
}