How to Sort a Linked List by Converting to Array/Vector?
- Time:2020-09-12 10:06:27
- Class:Weblog
- Read:24
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:Find the largest palindrome From the product of two 3-digit numb
What is the largest prime factor of the number 600851475143 ?
Can we Construct K Palindrome Strings?
Sum of Even Fibonacci Numbers
Sum of Multiples of 3 and 5
How to Design Underground System using Several Hash Maps?
How to Remove Zero Sum Consecutive Nodes from Linked List using
Depth First Search and Breadth First Search Algorithm to Open th
Dynamic Programming (Memoization) to Sort Integers by The Power
Applicable Accounting Software For Churches
- Comment list
-
- Comment add