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) —

推荐阅读:
Facebook Onsite Interview Preparation Part 1: Motivation/Bahavio  Celebrate WordPress’ 13th Birthday With These Interesting Facts  5 Ways to Use Your Smartphone to Build a Better Blog  The Most Expensive Domain Sales Ever  15 Ways Of How Not To Kill Your Leadership Authority  Study Shows Strong Growth of Tech Inventions to Fight Climate Ch  Interested in Bitcoins? Here are 10 Blogs You Need to Check Out  Your Blog’s Been Hacked! Here’s What You Need to Do  #DiningForBrussels: How Belgium Is Fighting Terrorism With A For  Many WordPress Site Hackings Caused To These Plugins 
评论列表
添加评论