在 Java 链表中排序

Question

我试图在java中实现链表。我正在尝试对其进行排序。

该计划如下

class Link{
int data1;
String data2;
Link nextLink;
Link(int d1, String d2){
    data1=d1;
    data2=d2;
    nextLink=null;
}
void printLink(){
    System.out.println("{"+data1+", "+data2+"}");
}
}
class LinkList{
Link first;
LinkList(){
    first=null;
}
void insert(int d1, String d2){
    Link list=new Link(d1,d2);
    list.nextLink=first;
    first=list;
}
void printList(){
    Link currentLink=first;
    while(currentLink!=null){
        currentLink.printLink();
        currentLink=currentLink.nextLink;
    }
}
}
public class men{
    public static void main(String args[]){
        LinkList l1= new LinkList();
        l1.insert(10,"ABC");
        l1.insert(20,"DEF");
        l1.printList();
    }
}

我想按元素data1排序。

Answer 1

一个简单的方法是从一个新的空列表开始，该列表将成为排序列表。从原始列表中删除节点，然后按顺序插入到新列表中。

最快的方法是自下而上的合并排序的变体，使用一个小的（26 到 32）引用（指针）数组到排序列表的第一个节点，其中 array[i] 为 0（null）或指向其中的 power i 节点具有 2 的列表。原始列表中的所有节点一次合并到数组中，然后合并数组以形成单个排序列表。在这篇 Wiki 文章中，merge（） 函数合并了两个已经排序的列表，并处理一个或两个列表为空的情况以简化主代码：

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Answer 2

我迟到了，但这是 java 中的实现。 希望有帮助。

 class men{
    public static void main(String args[]){
        LinkList l1= new LinkList();
        l1.insert(10,"ABC");
        l1.insert(20,"DEF");
        l1.insert(30, "GHI");
        l1.insert(40, "JKL");
        l1.insert(5, "hhh");
        l1.printList();
        mergesort(l1);
        System.out.println("After sorting: ");
        l1.printList();
    }
    private static void mergesort(LinkList l1) {
        // TODO Auto-generated method stub
        //Link curr=l1.first;
        if(l1.first!=null && l1.first.nextLink != null){
            Link middle= getMiddle(l1);
            if(middle == l1.first){
                //only two elements in the listt.just swap
                if(middle.data1>middle.nextLink.data1){
                    l1.first=l1.first.nextLink;
                    l1.first.nextLink=middle;
                    middle.nextLink=null;
                    //l1.printList();
                }
            }else{
                LinkList left=new LinkList();
                LinkList right=new LinkList();
                left.first=l1.first;
                right.first=middle.nextLink;
                middle.nextLink=null;
                mergesort(left);
                mergesort(right);
                Link cur_left=left.first;
                Link cur_right=right.first;
                l1.first=null;
                Link last=null;
                while(true){
                    if((cur_left !=null) && (cur_right !=null)){
                         if (cur_left.data1>cur_right.data1){
                             last=l1.insertAtLast(cur_right.data1, cur_right.data2, last);
                             cur_right=cur_right.nextLink;
                         }else{
                             last=l1.insertAtLast(cur_left.data1, cur_left.data2, last);
                             cur_left=cur_left.nextLink;
                         }
                    }else if(cur_left !=null){
                        last=l1.insertAtLast(cur_left.data1, cur_left.data2, last);
                        cur_left=cur_left.nextLink;
                    }else if(cur_right !=null){
                        last=l1.insertAtLast(cur_right.data1, cur_right.data2, last);
                        cur_right=cur_right.nextLink;
                    }else break;
                }
            }
        }
    }
    private static Link getMiddle(LinkList l1) {
        // TODO Auto-generated method stub
        if(l1.first== null){return l1.first;}
        Link slow,fast;
        slow=fast=l1.first;
        while(fast.nextLink !=null && fast.nextLink.nextLink !=null){
            slow=slow.nextLink;
            fast=fast.nextLink.nextLink;
        }
        return slow;
    }
}