这题，选择排序时间复杂度过不了吧…… import java.util.*;
public class Solution {
public ListNode sortInList (ListNode head){
if(head == null || head.next == null)
return head;
ArrayList space = new ArrayList<>();
for (ListNode walker = head;walker!=null;walker = walker.next)
space.add(walker.val);
space.sort(Integer::compareTo);
int i=0;
for (ListNode walker = head;walker!=null;walker = walker.next)
{
walker.val = space.get(i++);
}
return head;
}
//选择排序，遍历链表 选择最小的节点放到最前面
public ListNode sortInListReal (ListNode head) {
// write code here
ListNode pre=new ListNode(0);
ListNode newHeadPre=pre;
pre.next=head;
ListNode index=pre;
ListNode minNode=head;
ListNode minPre=pre;
while(pre.next!=null){
while(index.next!=null){
if(index.next.val
minPre=index;
minNode=index.next;
}
index=index.next;
}
if(minNode==pre.next){
pre=pre.next;
}else{
//记录下一个遍历节点
//ListNode next=pre.next;
//最小节点前置插入
//pre.next=minNode;
//最小节点删除
//minPre.next=minPre.next.next;
//minNode.next=next;
int tmp=pre.next.val;
pre.next.val=minNode.val;
minNode.val=tmp;
pre=pre.next;
}
index=pre;
minNode=pre.next;
minPre=pre;
}
return newHeadPre.next;
}
}