如何使用LinkedList实现合并排序？

Question

我正在尝试使用LinkedList实现合并排序，到目前为止，

class Node{


Node next;
int data;

public Node (){

}

public Node(int _data){

    this.data = _data;
   }
  }


 public  class myTest{

   private static Node head;
   private static Node current; 

   public void myTest(){

    this.head = null;
    this.current = null;
}

public static void insert( int data ){

    Node newNode = new Node(data);

    if (head == null){

        head = newNode;
        current = head;
    }

    else {

        current.next = newNode;
        current = newNode;
    }
}

public static void display(Node cur ){

    while( cur != null){

        if (cur.next != null){
            System.out.print(cur.data + " -> ");
        }

        else{
            System.out.print(cur.data +" ");
        }

        cur = cur.next;
    }

    System.out.println();
}

private static Node mergeSort(Node headOriginal ){

    if (headOriginal == null || headOriginal.next == null ){

        return headOriginal; 
    }

    Node a = headOriginal;
    Node b  = headOriginal.next;

    while( b != null && b.next != null ){

        headOriginal = headOriginal.next;
        b = (b.next).next;
    }

    // split in 2 parts 
    b = headOriginal.next;
    headOriginal.next = null;

    return merge( mergeSort(a), mergeSort(b) );
}


 // sort among the 2 parts
 public static Node merge(Node a, Node b) {

    Node c = new Node();
    Node head_1 = c;

    while ((a != null) && (b != null)) {

        if ( a.data <= b.data ){

            c.next = a;
            c = a;
            a = a.next;
        }

        else {

            c.next = b;
            c = b;
            b = b.next;
        }
    }

    c.next = (a == null) ? b : a;
    return head_1.next;        
}  

public static void main(String[] args ){

    int [] arr = {12, 34, 5, 6, 7};

    for (int j =0; j < arr.length; j++){

        insert( arr[j] );
    }

    mergeSort(head);
    display(head);

  }
}

mergeSort函数取LikedList的原始头，LikedList由insert函数生成。我认为该函数正确地创建了升序的排序LL。显示功能假设打印LL。在这种情况下，它仅从原始磁头（12）打印到已排序的LL的末端，并打印'12'-

1. 我的程序是否正常，或者需要一些改进来实现合并排序

Answer 1

我想这是出于学术目的，因为Sandeep的评论是正确的，LinkedList不是mergesort的合适数据结构。编写自己的链表也可能不是一个好主意，因为Java API数据结构设计良好，测试良好！

但是对于您的代码，它工作得非常好！唯一的错误是，您使用的不是mergesort的结果，而是对head的“旧”引用。如果你更新你的参考资料，应该没问题。尝试：

head = mergeSort(head);
display(head);

在你的主要方法中，它应该按预期工作！