使用linkedList的mergesort算法无法在Java中正确实现

Question

我已经为一个自定义的LinkedIntList实现了mergesort方法，它只不过是一个LinkedList类。我很难理解它为什么失败。也就是说，它不会产生任何结果。我把代码检查了好几次，都弄不明白

代码如下：

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;
 }
}

LinkedIn列表类：

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;
    }
}

测试此功能的实用程序类：

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);

     }
}

输出：--->

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

Answer 1

至少部分问题在这里：

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

如果当前节点为null，则应返回null， 但是，如果节点。如果next为null，则应返回node

考虑列表（3, 2）

的情况

列表节点为（节点[3]，下一个->；节点[2]，下一个->；[NULL]）

您可以使用Walker=（节点[3]，Next->；[NULL]）和Runner=（节点[2]，Next->；[NULL]）来打破列表

然后在Walker（重命名为左侧）和Runner（重命名为右侧）上调用合并排序

它位于这些调用的每个节点上。下一个测试为null，因此它返回null，而不是您想要的列表，它应该是传入的列表

存在一个错误，该错误将在合并方法中生成空指针异常。。你能找到它吗