148 Sort List

一開始我想, 這不就是一般的merge sort 只不過用linded list表示, 後來被一個很大的測資表了

但時間複雜度我沒有出錯啊, 到底是哪邊呢

附上原本的code

class Solution {
  public:
    static int listlength(ListNode *head) {
        int count = 0;
        while (head) {
            head = head->next;
            count++;
        }
        return count;
    }
    static ListNode *merge(ListNode *a, ListNode *b) {
        ListNode *res = new ListNode(0);
        ListNode *head = res;
while (a && b) {
            if (a->val < b->val) {
                res->next = a;
                res = res->next;
                a = a->next;
            } else {
                res->next = b;
                res = res->next;
                b = b->next;
            }
        }
        if (a) {
            res->next = a;
        }
        if (b) {
            res->next = b;
        }
        return head->next;
    }
    ListNode *sorts(ListNode *head) {
        if (!head->next) {
            return head;
        }
        ListNode *tmp = head;
int len = listlength(head) / 2 - 1;
        while (len > 0) {
            tmp->next;
            len--;
        }
        ListNode *b = tmp->next;
        tmp->next = nullptr;
        ListNode *a = head;
        a = sorts(a);
        b = sorts(b);
        return merge(a, b);
    }
ListNode *sortList(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *res = sorts(head);
        return res;
    }
};

原來是在找中心點時我的找法太慢了, 這邊附上快慢指針的理解

一個每次都走兩步, 一個每次都走一步, 當快指針走到終點時, 慢指針剛好走到一半, 天才, 真的是天才

class Solution {
public:
    ListNode* merge(ListNode* a, ListNode*b){
        ListNode *root = new ListNode(0);
        ListNode *head = root;
        while(a && b){
            if(a->val < b->val){
                root->next = a;
                a = a->next;
                root = root->next;
            }else{
                root->next = b;
                b = b->next;
                root = root->next;
            }
        }
        if(a){
            root->next = a;
        }
        if(b){
            root->next = b;
        }
        return head->next;
    }
    ListNode* sortList(ListNode* head) {
        if(!head){
            return head;
        }
        if(!head->next){
            return head;
        }
        ListNode *slow = head;
        ListNode *fast = head;
while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
ListNode *left = sortList(head);
        ListNode *right = sortList(fast);
return merge(left, right);
    }
};