Saturday, May 11, 2013

Rotate List in C++



Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.



Solution:
ListNode *rotateRight(ListNode *head, int k) {
        if(!head)
        return NULL;
        ListNode* quick = head;
        int len = 1;
        while(head->next)
        {
            head = head->next;
            len++;
        }
        head->next = quick;
        k = k%len;
        k = len - k;
        int cur = 1;
        while(cur < k)
        {
            quick = quick->next;
            cur++;
        }
        ListNode* newhead = quick->next;
        quick->next = NULL;
        return newhead;
    }

No comments:

Post a Comment