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:
How to Optimize Your Content Marketing for SEO
The Top Client-Attraction Strategies
Side Hustle Tips for the Social Media Savvy
A Quick Guide To Creating A User Persona For Your Blog
7 Top Image Compression Plugins For Your WordPress Blog
3 Ways to Convert Blog Readers to Leads
7 Ways To Deal With AdBlock Users If You’re A Blogger
2020 Design Trends [Infographic]
8 Content Marketing Plugins You Need For Your WordPress Blog
Tips to Make Money from the Comfort of Your Own Home
Share:Facebook Twitter
Comment list
Comment add