How to Sort a Linked List by Converting to Array/Vector?
- Time:2020-09-12 10:06:27
- Class:Weblog
- Read:28
Although, sorting a linked list can be done via Recursive Divide-and-Conquer algorithm i.e. merge sorting, we can however, turn the linked list into an array (or vector) using O(N) time and space, then sort the array/vector in O(nlogn), and finally convert it back to the linked list in O(n) time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* insertionSortList(ListNode* head) { if (head == NULL) return NULL; vector<int> data; ListNode *p = head; while (p) { data.push_back(p->val); p = p->next; } sort(begin(data), end(data)); p = head; for (const auto &n: data) { p->val = n; p = p->next; } return head; } }; |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* insertionSortList(ListNode* head) { if (head == NULL) return NULL; vector<int> data; ListNode *p = head; while (p) { data.push_back(p->val); p = p->next; } sort(begin(data), end(data)); p = head; for (const auto &n: data) { p->val = n; p = p->next; } return head; } };
We don’t need to allocate new nodes for the sorted singly-linked list. Instead, we can follow the original linked list in the same order of the sorted array, then synchronise the values from the array to the linked list. This will cost O(N) time and O(1) additional space.
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:C++ Coding Reference: std::accumulate() and examples
C++ Coding Reference: sort() and stable_sort()
The C++ Function using STL to Check Duplicate Elements/Character
How to Find Positive Integer Solution for a Given Equation using
How to Implement the instanceof in Javascript?
Azerbaijani Blogger, Mehman Huseynov Sentenced To Prison For All
Fitness Blog Shows Us All How Transformation Photos Can Be Decei
StickPNG: A Blogger’s Haven For Personal Use Images
5 Tips for Getting More Experience in Your Blogging Niche
Right-Wing Blogger Milo Yiannopoulos Resigns From Breibart
- Comment list
-
- Comment add