Reverse Nodes In K Group

January 10, 2025

Reverse Nodes In K Group Problem

You are given the head of a singly linked list and a positive integer k.

Reverse the first k nodes of the list, then reverse the next k nodes, and continue this process. If there are fewer than k nodes remaining, leave them as is.

Return the updated linked list with nodes reversed in groups of k, modifying only the nodes’ next pointers, not their values.

Examples related Reverse Nodes in K Group

Example 1:

Illustration 1: Input: head = [1,2,3,4,5,6], k = 3
Output: [3,2,1,6,5,4]

Example 2:

Example 2: Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

Length of the linked list is n.
1 <= k <= n <= 100
0 <= Node.val <= 100

Hints to Solve Reverse Nodes In K Group

Hint 1 :

Brute-force approach would involve storing node values in an array, reversing the groups one by one, and then converting it back to a linked list, which takes O(n) space.
Can you think of a more efficient way, perhaps by reversing the linked list in place without extra space?

Hint 2 :

We can reverse each group in place and keep track of the head of the next group.
For example, with a list like [1, 2, 3, 4, 5] and k = 2, we reverse [1, 2] to [2, 1], then [3, 4] to [4, 3], while correctly linking 1 to 4 and 3 to 5.
How can we efficiently manage these connections?

Hint 3 :

Use a dummy node to handle head modifications, pointing its next pointer to the current head.
Iterate k nodes, saving the next group’s head, and track the tail of the previous group.
After reversing the current group, reconnect the previous tail to the new head, and the current tail to the next group’s head.
Repeat this for all groups and return the new head of the list.

Recommendation for Time and Space Complexity (For Reverse Nodes In K Group)

Aim for a solution with O(n) time and O(1) space, where n is the length of the list.

There are mainly 2 approach to solve Reverse Nodes In K Group problem:

Recursion Method
Iteration Method

1. Recursion Method

In this approach, we recursively reverse the nodes in k-group chunks.
At each step, we reverse the first k nodes and then move to the next group.
Once we reach a group with fewer than k nodes, we stop and return the modified list.
Time complexity: O(n)
Space complexity: O(n/k)

Code:

C++

Java

Python

JavaScript

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int group = 0;
        while (cur != nullptr && group < k) {
            cur = cur->next;
            group++;
        }

        if (group == k) {
            cur = reverseKGroup(cur, k);
            while (group-- > 0) {
                ListNode* tmp = head->next;
                head->next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int group = 0;
        while (cur != null && group < k) { 
            cur = cur.next;
            group++;
        }

        if (group == k) { 
            cur = reverseKGroup(cur, k); 
            while (group-- > 0) { 
                ListNode tmp = head.next; 
                head.next = cur; 
                cur = head; 
                head = tmp; 
            }
            head = cur;
        }
        return head;
    }
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        group = 0
        while cur and group < k:
            cur = cur.next
            group += 1

        if group == k:
            cur = self.reverseKGroup(cur, k)
            while group > 0:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                group -= 1
            head = cur
        return head

JavaScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number} k
     * @return {ListNode}
     */
    reverseKGroup(head, k) {
        let cur = head;
        let group = 0;
        while (cur && group < k) {
            cur = cur.next;
            group++;
        }

        if (group === k) {
            cur = this.reverseKGroup(cur, k);
            while (group-- > 0) {
                let tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
}

2. Iteration Method

Iteration method involves reversing k nodes in a group iteratively.
For each group, we reverse the nodes one by one while keeping track of the necessary pointers to reconnect the groups.
This approach avoids recursion and works in-place.
Time complexity: O(n)
Space complexity: O(1)

Code:

C++

Java

Python

JavaScript

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* groupPrev = dummy;

        while (true) {
            ListNode* kth = getKth(groupPrev, k);
            if (!kth) {
                break;
            }
            ListNode* groupNext = kth->next;

            ListNode* prev = kth->next;
            ListNode* curr = groupPrev->next;
            while (curr != groupNext) {
                ListNode* tmp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = tmp;
            }

            ListNode* tmp = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = tmp;
        }
        return dummy->next;
    }

private:
    ListNode* getKth(ListNode* curr, int k) {
        while (curr && k > 0) {
            curr = curr->next;
            k--;
        }
        return curr;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true) {
            ListNode kth = getKth(groupPrev, k);
            if (kth == null) {
                break;
            }
            ListNode groupNext = kth.next;

            ListNode prev = kth.next;
            ListNode curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            ListNode tmp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = tmp;
        }
        return dummy.next;
    }

    private ListNode getKth(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

JavaScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number} k
     * @return {ListNode}
     */
    reverseKGroup(head, k) {
        const dummy = new ListNode(0, head);
        let groupPrev = dummy;

        while (true) {
            const kth = this.getKth(groupPrev, k);
            if (!kth) {
                break;
            }
            const groupNext = kth.next;

            let prev = kth.next;
            let curr = groupPrev.next;
            while (curr != groupNext) {
                const tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            const tmp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = tmp;
        }
        return dummy.next;
    }

    getKth(curr, k) {
        while (curr && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

Unlock this article for Free,
by logging in

Reverse Nodes In K Group