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;

}

It would be tough to provide context without any runnable code here, given that the issue you describe is runtime in nature. — Makoto
– Makoto, Commented Sep 21, 2018 at 1:01
you can just paste my code in the above link of leetcode to see the result — user3239558
– user3239558, Commented Sep 21, 2018 at 1:03

samabcde · Accepted Answer · 2018-09-21 01:46:30Z

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.

answered Sep 21, 2018 at 1:46

samabcde

8,3043 gold badges30 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

nupadhyaya · Accepted Answer · 2018-09-21 01:35:35Z

0

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;

}
}

answered Sep 21, 2018 at 1:35

nupadhyaya

1,9441 gold badge14 silver badges14 bronze badges

Collectives™ on Stack Overflow

java: Memory Limit Exceeded?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related