My O(n) solution has runtime error?


  • 0
    E

    I don't understand why my first solution got a runtime error, the algorithm uses only O(n) time. My second solution uses O(2*n-k) time, but it passed with runtime 12ms. Does this mean building a vector will cost so much time?

    solution1

    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* tmp = head;
        vector<ListNode*> a;
        while (tmp!=NULL) {
            a.push_back(tmp);
            tmp = tmp->next;
        }
        int n = a.size();
        k %= n;
        ListNode* result = a[n-k];
        a[n-1]->next = a[0];
        a[n-k-1]->next = NULL;
        return result;
    }
    

    solution2

    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* tmp1 = head;
        ListNode* tmp2 = head;
        int n = 1;
        while (tmp1->next != NULL) {
            tmp1 = tmp1->next;
            n++;
        }
        k %= n;
        for(int i = 1; i < n-k; i++)
            tmp2 = tmp2->next;
        tmp1->next = head;
        ListNode* result = tmp2->next;
        tmp2->next = NULL;
        return result;
    }

  • 0
    E

    when "k%n == 0", my first solution will make mistakes,
    and runtime error doesn't mean time limit exceeding.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.