题解 | #单链表的选择排序#

import java.io.;
import java.util.;

class Node{
public int value;
public Node next;
public Node(int data){
this.value=data;
}

//String数组转链表   非环
public  static Node tranStringNoLoop(String[] nums){
    Node head=new Node(Integer.parseInt(nums[0]));
    Node cur=head;
    for(int i=1;i<nums.length;i++){
        cur.next=new Node(Integer.parseInt(nums[i]));
        cur=cur.next;
    }
    return head;
}

//int数组转链表  非环
public  static Node tranIntegerNoLoop(int[] nums){
    Node head=new Node(nums[0]);
    Node cur=head;
    for(int i=1;i<nums.length;i++){
        cur.next=new Node(nums[i]);
        cur=cur.next;
    }
    return head;
}

//打印链表[非环]
public static  void printNodeList(Node head){
    StringBuilder sb=new StringBuilder();
    while (head!=null){
        sb.append(head.value).append(" ");
        head=head.next;
    }
    System.out.println(sb.toString());
}

}

public class Main{
public static Node selectionSort(Node head){
Node tail=null; //排序部分尾部
Node cur=head; //未排序部分头部
Node smallPre=null; //最小节点的前一个节点
Node small=null; //最小的节点

    while(cur!=null){
        small=cur;
        smallPre=getSmallestPreNode(cur);
        if(smallPre!=null){
            //删除最小的节点
            small=smallPre.next;
            smallPre.next=small.next;
        }
        //如果最小节点为当前节点，改变头；否则不变
        cur= cur==small?cur.next:cur;
        //将small连接到排序部分尾部
        if(tail==null){
            head=small;
        }else{
            tail.next=small;
        }
        tail=small;
    }

    return head;
}

public static Node getSmallestPreNode(Node head){
    Node smallPre=null;
    Node small=head;
    Node pre=head;
    Node cur=head.next;

    while(cur!=null){
        if(cur.value<small.value){
            smallPre=pre;
            small=cur;
        }
        pre=cur;
        cur=cur.next;
    }
    return smallPre;

}

public static void main(String[]args)throws IOException{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    in.readLine();
    String[] nums=in.readLine().split(" ");
    Node head=Node.tranStringNoLoop(nums);
    head=selectionSort(head);
    Node.printNodeList(head);
}

}