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:
Summits set epoch-making milestone in history of China-Arab ties
In the face of COVID-19 pandemic, China and Arab countries have
15 Macao residents qualify as candidates for deputies to nationa
Study finds genetic solution to pre-harvest sprouting in rice, w
Bodybuilders dying as coaches, judges encourage extreme measures
Malta's Marsaskala, China's Dujiangyan sign sister city agreemen
U.S. mortgage applications continue slide amid surging interest
Russian, UAE presidents discuss bilateral cooperation over phone
Hate crimes in U.S. Los Angeles County rise to highest level sin
Chinese mainland reports 4,031 new local confirmed COVID-19 case
Share:Facebook Twitter
Comment list
Comment add