Description

Given a singly linked list node, and an integer k, reverse every k contiguous group of nodes.

Constraints:

• n ≤ 100,000 where n is the number of nodes in node

Example 1

Input

node = [0, 1, 2, 3]
k = 2

Output

[1, 0, 3, 2]

Example 2

Input

node = [0, 1, 2, 3]
k = 3

Output

[2, 1, 0, 3]

Intuition

track: after you reverse a group of list, you need to link those groups together.

node->next = solve(curr, k)this node is the head before reverse, but after reverse it is the tail of current group of nodes

Implementation

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* node, int k) {
    LLNode *prev = NULL, *curr = node, *next = NULL;
    int times = k;
    while (times && curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        times--;
    }

    if (curr) {
        node->next = solve(curr, k);
    }
    return prev;
}

Time Complexity

• Time: O(n)
• Space: O(1)