Sharing my simple O(n) solution with explanation


  • 1
    Z
    ListNode *rotateRight(ListNode *head, int k) {
        if(head == nullptr){
            return nullptr;
        }
        ListNode* p1 = head;
        ListNode* p2 = head;
        int size = 1;
        while(p1->next != nullptr){
            p1 = p1->next;
            size++;
        }
        p1->next = head;
        for(int i = 0; i < size - k % size - 1; i++){
            p2 = p2->next;
        }
        p1 = p2->next;
        p2->next = nullptr;
        return p1;
    }
    

    In the first For loop, I make p1 point to tail node and count the size of this linked list. Then p1->next = head make this list become a circle.

    In the second For loop, I make p2 point to the previous node before the target node. Let the previous node point to nullptr and return target node.

    Tricky place: size - k % size - 1 can make pointer point to the previous node before the target node in O(n) time.


Log in to reply
 

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