Leetcode 148. Sort List | | Leetcode 148. Sort List 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950/** * 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; }}; Version 2 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/** * 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; }}; Reference https://leetcode.com/problems/sort-list/description/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏