LeetCode Reverse Nodes in k-Group

Question

Link: https://leetcode.com/problems/reverse-nodes-in-k-group/

Problem description:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

e.g. Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]

My solution:

/**
 * 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** subHead = &head;
        int i = 0;
        for (ListNode* subTail = head; subTail != NULL; subTail = subTail->next) {
            if ((i+1) % k == 0) {
                ListNode* temp = subTail->next;
                reverse(subHead, &subTail);
                subTail->next = temp;
                subHead = &(subTail->next);
            }
            i++;
        }
        return head;
    }
    
    void reverse(ListNode** subHead, ListNode** subTail) {
        if (*subHead==NULL) return;
          ListNode* itHead = *subHead;
          ListNode* prev = NULL;
          ListNode* next = NULL;
          ListNode* end = (*subTail)->next;
          while (itHead != end) {
            next = itHead->next;
            itHead->next = prev;
            prev = itHead;
            itHead = next;
          }
        std::swap(*subHead, *subTail);
    }
};

This solution was accepted and seemed to do quite well in both space and time. I'm interested in how it can be optimized further, how it can be made more readable, more elegant, or better express good design principles. Note that the data definition and the signature ListNode* reverseKGroup(ListNode* head, int k) is enforced by the question. Feel free to comment on anything you'd like though.

Answer 1

Don't use the macro NULL. Use the specific keyword nullptr now.

Your struct can be more simply written using immediate inline initializers.

struct ListNode {
    int val = 0;
    ListNode* next = nullptr;
    ListNode() = default;
    ListNode(int x) : val{x} {}
    ListNode(int x, ListNode* next) : val{x}, next{next} {}
};
 

Also note that the * goes with the type in C++, not with the name being declared.

Regarding
void reverse(ListNode** subHead, ListNode** subTail)
It appears that the names subHead and subTail are never modified by the code, so this would be easier if you passed references to the pointers, rather than having an extra explicit dereference operation when you use it.

ListNode* itHead = *subHead;
//...
while (itHead != end) {
    //...
    itHead = next;
}

This is just a for loop that's spread out for no reason. The value of next you want is lost during the body of the loop, so I can see why you don't put that inside a for construct. But you can put the declaration of subHead there... put the parts you can into a for loop, even if it's not all three of them.

Re:
if (*subHead==NULL) return;
Don't make explicit comparisons against null. Use the truth predicates that are part of the (possibly smart!) pointer.

Combining this with the tip of using references (...ListNode*& subHead,) you get simply: if (!subHead) return;.

Re:
std::swap(*subHead, *subTail);
This works because you know that these are raw pointers. But generally you write code like this as a template, or at least you code mostly as if you are writing a template, to ease future maintenance. If the type of something changes, the code should at best still work; second but still OK is cause a compile-time error that you must fix; but bad is to silently fail. Consider what would happen if these were not raw pointers but iterators of some type, including something supplied by your program or another library (not in std).

You need to use the so-called "std two-step" to use swap and a few others. Or, if using C++20 you can use std::ranges::swap instead. Always use swap etc. properly without relying on knowledge that the overload you want is indeed found in std.

Answer 2

Don't force-feed OOP.

class Solution is a symptom of OOP-braindamage. The only members are better off as free functions.

Beware that most coding-challenge sites promote an astonishing amount of bad ideas. Inefficiency by orders of magnitude is par for the course, and it gets worse.

Encapsulation

Too much leads to useless boilerplate. Specifically, a node should be a pure dumb struct, only containing data-members (links, in their own struct if both directions, and data, preferably in that order).

But the nodes should be encapsulated in a list-type.

Well, in this case as the point is playing with the innards, the enclosing type can be omitted, but it is a special case.

Almost Always auto

Don't complicate things by writing the exact type when nobody cares. Such duplication is at best tiresome, leading to more work when refactoring and often causing inefficient code.

Use minimum-strength operations

This way, you can avoid remainder %, and as a plus if there are more than INT_MAX nodes, you don't suffer from signed overflow, which is UB.

Boolean

Use implicit conversions. Use boolean algebra. Avoid explicit comparison, especially against true, which is easily done wrong.

auto reverseKGroup(ListNode* head, int k) {
    auto first = &head;
    int i = k;
    for (auto last = head; last; last = last->next) {
        if (!--i) {
            i = k;
            auto temp = last->next;
            reverse(first, &last);
            last->next = temp;
            first = &last->next;
        }
    }
    return head;
}

Don't add debug-code to the normal flow

Let assert() shine in its true role.

Know the standard library

std::iter_swap() incorporates the two-step needed for std::swap() before C++20 for pointees.