首页 > 代码库 > Sort List

Sort List

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

分析:merge sort。

class Solution {public:    ListNode *sortList(ListNode *head) {        if(head == NULL || head->next == NULL) return head;        int len = 0;        for(ListNode * p = head; p; p = p->next)            len++;                return mergeSort(head, len);    }        ListNode * mergeSort(ListNode * head, int l){        if(l == 0) return NULL;        if(l == 1) return head;                int l_len = l/2;        int r_len = l - l_len;                ListNode * p = head;        for(int i = 0; i < l_len -1; i++)            p = p->next;        ListNode * r_head = p->next;        p->next = NULL;                ListNode * l_list = mergeSort(head, l_len);        ListNode * r_list = mergeSort(r_head, r_len);                return merge(l_list, r_list);    }        ListNode * merge(ListNode * left, ListNode * right){        ListNode * dummy = new ListNode(-1);        ListNode * p = dummy;        while(left || right){            int lv = left?left->val:INT_MAX;            int rv = right?right->val:INT_MAX;                        if(lv <= rv){                p->next = left;                left = left->next;            }else{                p->next = right;                right = right->next;            }            p = p->next;        }        return dummy->next;    }};

 

Sort List