1，空间复杂度 O(n)
C++：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
std::vector<ListNode *> arrNode;
ListNode *node = head;
while ( node ) {
if ( arrNode.empty() ) {
arrNode.push_back( node );
} else {
bool inserted = false;
int i = 0, j = arrNode.size() - 1;
for ( ; i < j; ++i, --j ) {
if ( arrNode[i] -> val >= node -> val ) {
arrNode.insert( arrNode.begin() + i, node );
inserted = true;
break;
} else if ( arrNode[j] -> val <= node -> val ) {
arrNode.insert( arrNode.begin() + j + 1, node );
inserted = true;
break;
}
}
if ( !inserted ) {
if ( arrNode[i] -> val >= node -> val ) {
arrNode.insert( arrNode.begin() + i, node );
} else {
arrNode.insert( arrNode.begin() + i + 1, node );
}
}
}
node = node -> next;
}
ListNode *returnedHead = NULL;
for ( int i = 0; i < arrNode.size(); ++i ) {
if ( !returnedHead ) {
returnedHead = arrNode[i];
}
if ( i == arrNode.size() - 1 ) {
arrNode[i] -> next = NULL;
} else {
arrNode[i] -> next = arrNode[i + 1];
}
}
return returnedHead;
}
};
2，O(1)
C++：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode *node = head;
ListNode *previousNode = NULL;
ListNode *newHead = NULL;
while ( node ) {
if ( previousNode ) {
if ( previousNode -> val < node -> val ) {
ListNode *enumerateNode = previousNode;
while ( enumerateNode -> next && enumerateNode -> next -> val < node -> val ) {
enumerateNode = enumerateNode -> next;
}
ListNode *next = node -> next;
node -> next = enumerateNode -> next;
enumerateNode -> next = node;
previousNode = node;
node = next;
} else if ( previousNode -> val > node -> val ) {
if ( newHead -> val >= node -> val ) {
ListNode *next = node -> next;
node -> next = newHead;
newHead = node;
previousNode = node;
node = next;
} else {
ListNode *enumerateNode = newHead;
while ( enumerateNode -> next && enumerateNode -> next -> val < node -> val ) {
enumerateNode = enumerateNode -> next;
}
ListNode *next = node -> next;
node -> next = enumerateNode -> next;
enumerateNode -> next = node;
previousNode = node;
node = next;
}
} else {
// previousNode -> val == node -> val
ListNode *next = node -> next;
node -> next = previousNode -> next;
previousNode -> next = node;
previousNode = node;
node = next;
}
} else {
newHead = node;
previousNode = newHead;
node = node -> next;
newHead -> next = NULL;
}
}
return newHead;
}
};
