首页 > 代码库 > 【原创】leetCodeOj --- Sort List 解题报告

【原创】leetCodeOj --- Sort List 解题报告

今日leetcode链表题全制霸

 

原题地址:

https://oj.leetcode.com/problems/sort-list/

 

题目内容:

Sort List

 

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

 

方法:

 

题目要求是链表排序,同时时间复杂度要求O(n log n),空间复杂度要求常数空间。这意味着你不可以把链表拷贝到数组中,用一个map保留值和指针的对应关系,最后在构造一个链表。

我们需要考察不同的排序算法,看看哪种排序算法可以处理链表。关键在于哪种排序算法对于随机访问的依赖度低。

快排:首位指针,排除

堆排:要有两个儿子,排除

 

那就只能用归并排序了。

这次先给代码再分析复杂度

 

全部代码:

/** * 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 NULL;        int len = countLength(head);        if (len == 1)            return head;        int mid = len / 2;        ListNode *sec = dividedLst(head,mid);        head = sortList(head);        sec  = sortList(sec);        head = mergeList(head,sec);        return head;    }        ListNode *mergeList(ListNode *lst1,ListNode *lst2)    {        if (!lst2)            return lst1;        if (!lst1)            return lst2;        ListNode *ptr_lst1 = lst1;        ListNode *ptr_lst2 = lst2;        ListNode *begin = (ListNode *)malloc(sizeof(ListNode));        ListNode *tail  = begin;        tail->next = NULL;        while (ptr_lst1 && ptr_lst2)        {            if (ptr_lst1->val < ptr_lst2->val)            {                tail->next = ptr_lst1;                ptr_lst1   = ptr_lst1->next;                tail->next->next = NULL;                tail = tail->next;            }            else            {                tail->next = ptr_lst2;                ptr_lst2   = ptr_lst2->next;                tail->next->next = NULL;                tail = tail->next;            }        }        if (!ptr_lst1 && ptr_lst2) // lst1 is empty and lst2 has some            tail->next = ptr_lst2;        if (!ptr_lst2 && ptr_lst1) // lst1 has some and lst2 is empty            tail->next = ptr_lst1;        return begin->next;    }        int countLength(ListNode *head)    {        int count = 0;        while (head)        {            count ++;            head = head->next;        }        return count;    }        ListNode *dividedLst(ListNode *lst1,int mid)    {        ListNode *pre = lst1;        int count = 0;        while (lst1)        {            if (mid == count)            {                pre->next = NULL;                return lst1;            }            count ++;            pre = lst1;            lst1 = lst1->next;        }    }};

sort函数中,计算长度是n,合并是n,找中点是n/2,常数个n还是n

 

因此时间复杂度就是O(n log n)

【原创】leetCodeOj --- Sort List 解题报告