Leetcode: Sort List
2023-09-11 14:20:13 时间
Sort a linked list in O(n log n) time using constant space complexity.
/** * 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) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(head == NULL|| head->next == NULL)return head; map<int, vector<ListNode*>> mp; ListNode* pnode = head; while(pnode) { mp[pnode->val].push_back(pnode); pnode = pnode->next; } map<int, vector<ListNode*>>::iterator it = mp.begin(); head = NULL; ListNode* cur = NULL; for(; it != mp.end(); it++) { vector<ListNode*> vec = (*it).second; for(int i = 0; i < vec.size(); i++) { if(head == NULL){ head = vec[i]; cur = vec[i]; }else{ cur->next = vec[i]; cur = cur->next; } } } cur->next = NULL; return head; } };
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- leetcode 之Reverse Linked List II(15)
- Java实现 LeetCode 820 单词的压缩编码(暴力)
- (LeetCode 82)Remove Duplicates from Sorted List II
- (LeetCode 86)Partition List
- (LeetCode 203)Remove Linked List Elements
- [LeetCode] Flatten Nested List Iterator
- [LeetCode] Single Number II
- [LeetCode] Happy Number
- [LeetCode] Remove Linked List Elements
- [LeetCode] Insertion Sort List
- LeetCode(78):子集
- Leetcode 258. 各位相加
- Leetcode 2271. 毯子覆盖的最多白色砖块数(只有思路)
- [LeetCode] 83. Remove Duplicates from Sorted List ☆(从有序链表中删除重复项)
- [LeetCode] Linked List Cycle II