博客

描述

给定一个无序单链表，实现单链表的选择排序(按升序排序)。

要求：额外空间复杂度是O(1)。

输入描述：

第一行一个整数 n，表示单链表的节点数量。

第二行 n 个整数 val 表示单链表的各个节点。

输出描述：

在给出的函数内返回给定链表的头指针。

示例

输入：

5
1 3 2 4 5

输出：

1 2 3 4 5

解题思路：额外空间复杂度是O(1)代表着不能用额外的数据结构。在有限的几个变量里对链表实现选择排序。选择排序就是在未排序部分里找出最小的那个数，然后放到排好序部分的末尾。逐渐将未排序的部分缩小，最后全变成排好序的部分。

import java.util.Scanner;
import java.util.HashSet;

class Node{
    public int value;
    public Node next;
    public Node(int value){
        this.value=value;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String[] n=in.nextLine().split(" ");
        String[] num=in.nextLine().split(" ");
        
        Node node=transForNode(num);
        
        Node nodeF=selectionSort(node);
        
        show(nodeF);
    }
    //打印链表
    public static void show(Node head){
        while(head!=null){
            System.out.print(head.value+" ");
            head=head.next;
        }
        System.out.println();
    }
    //数组转链表
    public static Node transForNode(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;
    }
    
    //
    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;
            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 cur=head.next;
        Node pre=head;
        while(cur!=null){
            if(cur.value<small.value){
                smallPre=pre;
                small=cur;
            }
            pre=cur;
            cur=cur.next;
        }
        return smallPre;
    }
}