Leetcode-Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.

Explain

看题目要求,第一个是链表,第二个是时间复杂度为O(n log n),空间复杂度为O (1)。排序算法中说到这个时间复杂度的话,肯定也就会想到快排和归并排序。归并排序如果用数组实现的话,是做不到空间复杂度O(1)的,但是这刚好是用链表来实现的,所以用归并排序O(1)可以达到要求

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        if (!head->next) return head;
        return parti(head);
    }
    
    ListNode* parti(ListNode* cur) {
        if (!cur) return NULL;
        if (!cur->next) return cur;
        int len = 0;
        ListNode* temp = cur;
        while(temp) {
            temp = temp->next;
            len++;
        }
        
        int mid = len / 2;
        int count = 1;
        temp = cur;
        while(count < mid) {
            temp = temp->next;
            count++;
        }
        
        ListNode* next = temp->next;
        temp->next = NULL;
        
        ListNode* one = parti(cur);
        temp = NULL;
        next = parti(next);
        
        while(one || next) {
            if (one && next) {
                
                if (one->val == next->val) {
                    if (!temp) {
                        temp = one;
                        cur = temp;
                    } else {
                        temp->next = one;
                    }
                    ListNode* tmp = one->next;
                    one->next = next;
                    one = tmp;
                    temp = next;
                    next = next->next;
                } else if (one->val > next->val) {
                    if (!temp) {
                        temp = next;
                        cur = temp;
                    } else {
                        temp->next = next;
                        temp = next;
                    }
                    next = next->next;
                } else {
                    if (!temp) {
                        temp = one;
                        cur = temp;
                    } else {
                        temp->next = one;
                        temp = one;
                    }
                    one = one->next;                    
                }
            } else if(one) {
                if (!temp) {
                    cur = one;
                } else {
                    temp->next = one;
                }
                break;
            } else if(next) {
                if (!temp) {
                    cur = next;
                } else {
                    temp->next = next;
                }
                break;                
            } else {
                cur = NULL;
            }
        }
        
        return cur;
    }
};

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • My code: My test result: 这次作业说实话不难,但是要完全写出来还是有点细节的。首先,一开始...
    Richardo92阅读 490评论 1 1
  • 题目:Sort a linked list in O(nlogn) time using constant spa...
    这是朕的江山阅读 147评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,769评论 0 33
  • 一场秋霜 一抹忧伤 作者:张馨之 笔名:馨之 秋风总是那么冰凉,冰凉是因为种下了一场秋霜,这场秋霜的冰凉会...
    馨之随笔阅读 523评论 0 0
  • 有的时候,欲望像花朵一样美丽,引诱着你一步步走向深渊。
    眠花城阅读 387评论 4 9