?
?
?
/**
*
Sort a linked list using insertion sort.
*
*/
public class InsertionSortList {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
// 21 / 21 test cases passed.
// Status: Accepted
// Runtime: 312 ms
// Submitted: 0 minutes ago
//时间复杂度O(n * n) 空间复杂度 O(1)
public ListNode insertionSortList(ListNode head) {
ListNode preHead = new ListNode(-1);
while(head != null) {
ListNode cur = preHead;
int val = head.val;
while(cur.next != null) {
if(cur.next.val >= val) {
break;
}
cur = cur.next;
}
ListNode curNext = cur.next;
cur.next = head;
head = head.next;
cur.next.next = curNext;
}
return preHead.next;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
?