2019-05-25 22:51:03
浏览数 (1)
1. Description
2. Solution
代码语言：javascript
复制/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head) {
return NULL;
}
vector<ListNode*> nodes;
ListNode* current = head;
while(current) {
int index = binarySearch(nodes, current->val);
nodes.insert(nodes.begin() index, current);
current = current->next;
}
ListNode* result = nodes[0];
current = nodes[0];
for(int i = 1; i < nodes.size(); i ) {
current->next = nodes[i];
current = current->next;
}
current->next = NULL;
return result;
}
private:
int binarySearch(vector<ListNode*>& nodes, int target) {
int left = 0;
int right = nodes.size() - 1;
while(left <= right) {
int mid = (left right) / 2;
if(nodes[mid]->val > target) {
right = mid - 1;
}
else if(nodes[mid]->val < target) {
left = mid 1;
}
else {
return mid;
}
}
return left;
}
};
代码语言：javascript
复制/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head || !head->next) {
return head;
}
ListNode* pre = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr;
ListNode* l1 = sortList(head);
ListNode* l2 = sortList(slow);
return mergeTwoLists(l1, l2);
}
private:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* ptrFirst = l1;
ListNode* ptrSecond = l2;
ListNode* head = new ListNode(0);
ListNode* current = head;
while(ptrFirst && ptrSecond) {
if(ptrFirst->val > ptrSecond->val) {
current->next = ptrSecond;
ptrSecond = ptrSecond->next;
}
else {
current->next = ptrFirst;
ptrFirst = ptrFirst->next;
}
current = current->next;
}
if(ptrFirst) {
current->next = ptrFirst;
}
if(ptrSecond) {
current->next = ptrSecond;
}
return head->next;
}
};
