My 8ms O(n) time cpp code


  • -1
    C
    class Solution {
    public:
    
        ListNode* rotateRight(ListNode* head, int k) 
        {
            if(!head || !k) return head;
            
            // find tail and count the length
            int cnt = 1;
            ListNode *tail = head;
            while(tail->next)
            {
                cnt++;
                tail = tail->next;
            }
            
            k %= cnt;
            k = cnt - k;
            
            if(k == cnt) return head;
            
            // find first part
            ListNode *kth_node = head;
            while(--k)
                kth_node = kth_node->next;
            
            // rotate
            ListNode *new_head = kth_node->next;
            tail->next = head;
            kth_node->next = NULL;
            
            return new_head;
        }
    };

Log in to reply
 

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