C++ 8ms solution (<=2 passes over the list)


  • 0
    C
        ListNode* rotateRight(ListNode* head, int k) {
            if (k == 0 || head == NULL || head->next == NULL)
                return head;
            ListNode *iter1 = head, *iterk = head;
            /* Get iterk k nodes ahead of iter1 */
            int i;
            for (i = 0; i < k; i++) {
                if (iterk->next == NULL)
                    break;
                iterk = iterk->next;
            }
            /* 
            The list has less than k nodes. Take k % i and put that many
            nodes between iter1 and iterk 
            */
            if (i != k) {
                k = k % (i + 1);    
                return rotateRight(head, k);
            }
            /* Find the point to break off the list */
            while(iterk->next != NULL) {
                iter1 = iter1->next;
                iterk = iterk->next;
            }
            /* Rejoin iter1 to the head to complete the rotation */
            ListNode *retnode = iter1->next;
            iter1->next = NULL;
            iterk->next = head;
            return retnode;
        }

Log in to reply
 

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