How to Sort a Linked List by Converting to Array/Vector?
- 时间:2020-09-12 10:06:27
- 分类:网络文摘
- 阅读:78 次
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) —
推荐阅读:Dead Simple Ways to Keep Your Best Blogging Ideas From Slipping The Fear of Blogging is Real – Here’s How to Overcome It Influential Cybersecurity Blogger Gets Digitally Attacked Building Relationships with Your Influencers Authorities In Vietnam Arrest Top Blogger For One Criticizing Co The Top Health Bloggers You Should Be Following Mashable Blogger: Owning a Samsung Galaxy Note 7 is Safer Than G 5 Ways to Earn Money from Your Website Singapore Blogger Sentenced To Jail For Social Media Posts Comparing Left and Right Branch of a Complete Binary Tree
- 评论列表
-
- 添加评论