Back to solutions

Reverse Nodes in k-Group

HardLinked List

Reverse the nodes of a linked list k at a time. Nodes that do not form a complete group of k are left as is.

Open problem
Constraints
  • 1 <= k <= size <= 5000
  • 0 <= Node.val <= 1000

Group reversal with a dummy node

Time O(n)Space O(1)

Count k nodes ahead to confirm a full group exists, reverse that group, and splice it back. A group-previous pointer connects reversed groups in order.

struct ListNode { int val; ListNode* next; };

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy{0, head};
    ListNode* groupPrev = &dummy;
    while (true) {
        ListNode* kth = groupPrev;
        for (int i = 0; i < k && kth; i++) kth = kth->next;
        if (!kth) break;
        ListNode* groupNext = kth->next;
        ListNode* prev = groupNext;
        ListNode* cur = groupPrev->next;
        while (cur != groupNext) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode* tmp = groupPrev->next;
        groupPrev->next = kth;
        groupPrev = tmp;
    }
    return dummy.next;
}