2014
11-18

LeetCode-Insertion Sort List[排序]

Insertion Sort List

Sort a linked list using insertion sort.

// LeetCode, Insertion Sort List
// 时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
ListNode dummy(INT_MIN);

for (ListNode *cur = head; cur != nullptr;) {
auto pos = findInsertPos(&dummy, cur->val);
ListNode *tmp = cur->next;
cur->next = pos->next;
pos->next = cur;
cur = tmp;
}
return dummy.next;
}

ListNode* findInsertPos(ListNode *head, int x) {
ListNode *pre = nullptr;
for (ListNode *cur = head; cur != nullptr && cur->val <= x;
pre = cur, cur = cur->next)
;
return pre;
}
};


Java代码:

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public static ListNode insertionSortList(ListNode head) {
while(last != null){
ListNode nextNode = last.next;
while(insertNode.next != null){
if(last.val < insertNode.next.val)
break;
insertNode = insertNode.next;
}
last.next = insertNode.next;
insertNode.next = last;
last = nextNode;
}
}