I am getting Stack Overflow error using mergesort in java. Has anyone managed to do it similarly? Help!!


  • 0
    A
    public class Solution {
    public ListNode sortList(ListNode head) {
        if((head==null)||(head.next==null))
        {
            return head;
        }
        else
        {
            ListNode a = FrontbackSplit(head);
            ListNode left = sortList(head);
            ListNode right = sortList(a);
            return mergeTwoLists(left,right);
        }
    }
    
    int getLength(ListNode head)// Gives length of list
    {
        int n =0;
        if(head==null)
        {}
        else
        {
            n++;
            while(head.next!=null)
            {
                head = head.next;
                n++;
            }
        }
        return n;
    }
    
    ListNode getElement(ListNode start, int n)// Gives Nth element in List(element numbering starting from 0--start)
    {
        ListNode a = start;
        for(int i =0; i<n; i++)
        {
            a = a.next;
        }
        return a;
    }
    
    
    ListNode FrontbackSplit(ListNode head)
    {
        int length = getLength(head);
        ListNode c = getElement(head,(length/2)-1);
        ListNode d = c.next;
        c.next = null;
        return d;
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) // merges 2 sorted lists
    {
        if((l1==null)&&(l2==null))
        {return null;}
        else if((l1==null)&&(l2!=null))
        {
            return l2;
        }
        else if((l2==null)&&(l1!=null))
        {
            return l1;
        }
        else
        {
            if(l1.val<=l2.val)
            {
                ListNode head = new ListNode(l1.val);
                head.next = mergeTwoLists(l1.next,l2);
                return head;
            }
            else
            {
                ListNode head = new ListNode(l2.val);
                head.next = mergeTwoLists(l1,l2.next);
                return head;
            }
            
        }
    }
    

    }


  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    S

    Same here. Even I get stackOverFlow with recursive merge. whereas it works for c++


Log in to reply
 

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