java - 使用 linkedList 的合并排序无法正常工作 - 在 Java 中实现

Question

我已经为自定义 LinkedIntList 实现了合并排序方法，它只是一个 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;
 }
}

LinkedIntList 类:

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，但是，如果 node.next 为空，则应返回节点。

考虑列表 [3, 2] 的情况

列表节点是 (NODE [3], Next -> NODE [2], Next -> [NULL])

你用 Walker = (NODE [3], Next -> [NULL]) 和 Runner = (NODE [2], Next -> [NULL]) 打破列表

然后对 Walker(重命名为 Left)和 Runner(重命名为 Right)调用归并排序

在这些调用中的每一个中，Node.next 测试都是 null，因此它返回 null 而不是您想要的列表，这应该是传入的内容。

在merge方法中有一个会产生NULL Pointer Exception的bug..你能找到吗？