How to Sort a Linked List by Converting to Array/Vector?
- Time:2020-09-12 10:06:27
- Class:Weblog
- Read:25
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:The Vital Common Sense Marketing Strategy You May Have Forgotten
The 7 Features of a Successful Product Demo Video
Top Facebook Marketing Partner Comments On Facebook’s Newest Vid
Animoto Adds Square Video for Increased Social Media and Mobile
4 Things You Need to Know When Funding Your Freelance Business
How Dedicated Servers Boost the Performance of A Business Blog
Irish Travel Blogger Visits Every Country In The World, Just In
How to Build an Online Store on WordPress Using WooCommerce
C++ Coding Reference: is_sorted_until() and is_sorted()
Two Rectangles Overlap Detection Algorithm in C++
- Comment list
-
- Comment add