public class Solution {

    public static LinkedListNode<Integer> mergeSort(LinkedListNode<Integer> head) {
        //Your code goes 
         LinkedListNode slow=head, fast=head, temp=head;
         while(fast!=null && fast.next!=null){
             temp=slow;
             fast=fast.next.next;
             slow=slow.next;
         }
          temp.next=null;
          LinkedListNode left_side=mergeSort(head);
          LinkedListNode right_side=mergeSort(slow);

          return merge(left_side, right_side);
    }

    public static LinkedListNode merge(LinkedListNode<Integer> head1, LinkedListNode<Integer> head2){
       LinkedListNode temp_node=new LinkedListNode(0);
       LinkedListNode current_node= temp_node;

       while(head1!=null && head2!=null){
           if(head1.data<=head2.data){
               current_node.next=head1;
               head1=head1.next;
           }else{
               current_node.next=head2;
               head2=head2.next;
           }
           current_node=current_node.next;
       }
       if(head1!=null){
          current_node.next=head1;
          head1=head1.next;
       }
       if(head2!=null){
           current_node=head2;
           head2=head2.next;
       }
       
       return temp_node.next;


   }
}

I was expecting a sorted list but I'm getting a StackOverflowError.

How should I correct it? The error is shown specifically for the line where I call mergSort on the left side of the linked list. What should I do?

CodePudding user response：

You are using recursion in mergeSort() method and there is no exit condition for the mergeSort function. you should have an exit condition before calling recursion. Otherwise it will keep on calling the same method until the stack becomes full. thus stack overflow error.

CodePudding user response：

thumbs already answered the question. If interested, here are bottom up and top down merge sort single linked list examples. Bottom up is faster, how much faster depends on the size of the list and if the nodes are scattered. It's faster still to copy the list to an array, sort the array, then create a new sorted list from the array.

bottom up

    // merge two already sorted lists
    static Node temp = new Node();
    static Node merge(Node list0, Node list1) {
        if(list0 == null)
            return list1;
        if(list1 == null)
            return list0;
        Node dest = temp;
        while(true){
            if(list0.data <= list1.data){
                dest.next = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    break;
                }
            } else {
                dest.next = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    break;
                }
            }
        }
        return temp.next;
    }

    // bottom up merge sort for single link list
    static Node sortbu(Node head) {
        final int NUMLIST = 32;
        Node[] alist = new Node[NUMLIST];
        Node node;
        Node next;
        int i;
        // if < 2 nodes, return
        if(head == null || head.next == null)
            return null;
        node = head;
        // merge node into array
        while(node != null){
            next = node.next;
            node.next = null;
            for(i = 0; (i < NUMLIST) && (alist[i] != null); i  ){
                node = merge(alist[i], node);
                alist[i] = null;
            }
            if(i == NUMLIST)   // don't go past end of array
                i--;
            alist[i] = node;
            node = next;
        }
        // node == null
        // merge array into single list
        for(i = 0; i < NUMLIST; i  )
            node = merge(alist[i], node);
        return node;
    }

top down (note merge is identical to bottom up)

    // merge two already sorted lists
    static Node temp = new Node();
    static Node merge(Node list0, Node list1) {
        if(list0 == null)
            return list1;
        if(list1 == null)
            return list0;
        Node dest = temp;
        while(true){
            if(list0.data <= list1.data){
                dest.next = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    break;
                }
            } else {
                dest.next = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    break;
                }
            }
        }
        return temp.next;
    }

    // return size of list
    static int size(Node head) {
    int i = 0;
        while(head != null){
            head = head.next;
            i  ;
        }
        return i;
    }

    // advance to node n
    static Node advance(Node head, int n) {
        while(0 < n--)
            head = head.next;
        return head;
    }

    // top down merge sort for single link list entry function
    static Node sorttd(Node head) {
        int n = size(head);
        if(n < 2)
            return head;
        head = sorttdr(head, n);
        return head;
    }

    // top down merge sort for single link list recursive function
    static Node sorttdr(Node head, int n) {
        if(n < 2)
            return head;
        int n2 = (n/2);
        Node node = advance(head, n2-1);
        Node next = node.next;
        node.next = null;
        head = sorttdr(head, n2);
        next = sorttdr(next, n-n2);
        head = merge(head, next);
        return head;
    }