题意
给定一个无序单链表的头节点 head, 实现单链表的选择排序.
题解
按选择排序方法: 每次从原链表找出最小值, 从原链表删除, 插入新的有序链表.
时间复杂度 O(n^2) 额外空间复杂度 O(1)
代码
- public class Main {
- public static void main(String args[]) {
- Node n1=new Node(2);
- Node n2=new Node(1);
- Node n3=new Node(3);
- n1.next=n2;
- n2.next=n3;
- Node head=n1;
- Node sortHead=selectSort(head);
- Node pNode=sortHead;
- while(pNode!=null) {
- System.out.println(pNode.val);
- pNode=pNode.next;
- }
- }
- public static Node selectSort(Node head) {
- Node cur=head;// 无序链表头
- Node small=null;// 最小节点
- Node smallPre=null;
- Node tail=null;// 有序链表结尾
- while(cur!=null) {
- // 从原链表找 small 及删 small 节点
- smallPre=getSmallPreNode(cur);
- if(smallPre==null) {
- small=cur;
- }
- else {
- small=smallPre.next;
- smallPre.next=small.next;// 删除 small 节点
- }
- // 更新 cur 节点
- cur=cur==small?cur.next:cur;
- // 把 small 节点插入有序链表
- if(tail==null) {
- head=small;
- }
- else {
- tail.next=small;
- }
- tail=small;
- }
- return head;
- }
- public static Node getSmallPreNode(Node head) {
- Node small=head;
- Node smallPre=null;
- Node cur=head.next;
- Node pre=head;
- while(cur!=null) {
- if(cur.val<small.val) {
- small=cur;
- smallPre=pre;
- }
- pre=pre.next;
- cur=cur.next;
- }
- return smallPre;
- }
- }
[程序员代码面试指南] 链表问题 - 单链表的选择排序 (选择排序)
来源: http://www.bubuko.com/infodetail-3078699.html