在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（空）或指向一个列表，其中2个表示其中的节点。原始列表中的所有节点一次一个合并到数组中，然后合并数组以形成单个排序列表。在此维基文章，合并（）函数合并两个已排序的列表，并处理其中一个或两个列表是空的，简化了主代码的情况：

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