One time traverse


  • 0
    P

    '''
    class Solution {
    public:

    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return head;
        int count = 0, len = 0;
        ListNode *p1 = findPosition(head, k, count, len);
        if(p1->next==NULL){
            return head;
        }
        else{
            ListNode *p2 = p1->next;
            p1->next = NULL;
            ListNode *p3 = p2;
            while(p3->next!=NULL)
                p3 = p3->next;
            p3->next = head;
            return p2;
        }
    }
    ListNode* findPosition(ListNode* head, int &k, int &count, int &len){
        if(head == NULL){
            k = k%len;
            return head;
        }
        len++;
        ListNode *res = findPosition(head->next, k, count, len);
        if(k == count++)
            return head;
        return res;
    }
    

    };'''


  • 0
    A

    @peng60 Not really. First you traversed once in recursion, then you traversed a second time in main function.
    Besides, recursion uses at least O(n) stack space, even worse than simply storing all addresses in a vector.


Log in to reply
 

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