mergesort using linkedList not working correctly - implemented in Java

Question

I have implemented mergesort method for a custom LinkedIntList which is nothing but a LinkedList class. I am having difficulty in understanding why it fails. That is it does not produce any result. I gave gone through the code multiple times and I could not figure out.

Here is the code:

class ListNode {
 public int data;       // data stored in this node
 public ListNode next;  // link to next node in the list

 // post: constructs a node with data 0 and null link
 public ListNode() {
     this(0, null);
 }

 // post: constructs a node with given data and null link
 public ListNode(int data) {
     this(data, null);
 }

 // post: constructs a node with given data and given link
 public ListNode(int data, ListNode next) {
     this.data = data;
     this.next = next;
 }
}

LinkedIntList class:

public class LinkedIntList {
 public ListNode front;

 // Constructs an empty list.
 public LinkedIntList() {
     this(null);
 }

 public LinkedIntList(ListNode node){
     front=node;
 }

 public String toString() {
 if (front == null) {
     return "[]";
 } else {
     String result = "[" + front.data;
     ListNode current = front.next;
     while (current != null) {
         result += ", " + current.data;
         current = current.next;
     }
     result += "]";
     return result;
 }


  public void sort(){
     front=mergeSort(front); 
 }

    public ListNode mergeSort(ListNode node) {
        //ystem.out.println("merge sort is called");
        //first get middle of linkedlist, using two pointers
        //you can also get this by size/2

        //step 1: get middle pointers
        if (node==null || node.next==null)
            return null;
        ListNode runner=node.next.next;
        ListNode walker=node;
        while(runner!=null && runner.next!=null){
            runner=runner.next.next;
            walker=walker.next;
        }

        //At this point walker is in center
        ListNode right=walker.next;
        walker.next=null;
        ListNode left=node;
        left=mergeSort(left);
        right=mergeSort(right);

        node=merge(left,right);

        return node;
    }

    //merge of two linkedlist happens here
    private ListNode merge(ListNode l1, ListNode l2) {

        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }

        ListNode head=null;
        ListNode curr=null;
        ListNode temp=null;

        while(l1!=null && l2!=null){
            temp=(l1.data < l2.data ? l1 : l2);
            if (head==null){
                head=temp;
                curr=head;
            }
            else {
                curr.next=temp;
                curr=curr.next;
            }
            if (temp==l1){
                l1=l1.next;
            }
            else l2=l2.next;
        }
        if (l1!=null){
            curr.next=l1;
        }
        if (l2!=null){
            curr.next=l2;
        }

        return head;
    }
}

Utility Class that tests this:

public class UtilityMain {

     public static void main(String[] args){

         ListNode node5 = new ListNode(1,null);
         ListNode node4=new ListNode(2,node5);
         ListNode node3=new ListNode(3,node4);
         ListNode node2=new ListNode(4,node3);
         ListNode node1 = new ListNode(5,node2);

         LinkedIntList l = new LinkedIntList(node1);
         System.out.println("before sorting " + l);
             l.sort();
         System.out.println("Afer sorting " + l);

     }
}

Output: --->

before sorting [5, 4, 3, 2, 1]
             After sorting []

Answer 1

At least part of the problem is here:

if (node==null || node.next==null)
    return null;

If the current node is null, you should return null, However, if the node.next is null, you should return node.

Consider the case of a list [3, 2]

The list nodes are (NODE [3], Next -> NODE [2], Next -> [NULL])

You break the list with Walker = (NODE [3], Next -> [NULL]) and Runner = (NODE [2], Next -> [NULL])

and then call merge sort on both Walker (renamed to Left) and Runner (renamed to Right)

It is on each of these calls, the Node.next test is null and therefore it returns null and not the list you intend, which should be what was passed in.

There is a bug that will generate a NULL Pointer Exception in the merge method.. can you find it?