C solution (6ms) - O(1) space, O(n) time


  • 0
    • Before traversing k nodes, make sure k-nodes does exist.
    • As we reverse k-nodes in a group, maintain the current group tail and previous group tail.
    • At the end of every reversal point the previous group's tail to the current group's head (i.e the prev pointer)
    bool lessThanKNodes(struct ListNode *node, int k) {
        while (k-- > 0) {
            if (node == NULL) return true;
            node = node->next;
        }
        return false;
    }
    
    struct ListNode* reverseKGroup(struct ListNode* head, int k) {
        if (!head) return NULL;
        struct ListNode *curr = head, *next, *prev, *currGrpTail, *prevGrpTail = NULL;
        while (curr) {
            if (lessThanKNodes(curr, k)) {
                if (prevGrpTail) prevGrpTail->next = curr;
                return head;
            }
            currGrpTail = curr;
            int i = 0;
            prev = NULL;
            while (curr && i++ < k) {
                next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            if (prevGrpTail) {
                prevGrpTail->next = prev;
            } else {
                head = prev;
            }
            prevGrpTail = currGrpTail;
        }
        return head;
    }
    

Log in to reply
 

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