2
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks. So if I understand correctly, the only place where a ptr to ptr is really needed would be ListNode** subhead = &head? I think I see that reference to ptr would be better for the parameters of reverse. \$\endgroup\$
    – ShokoN
    May 27, 2021 at 17:31
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ What do you mean by minimum-strength operations? \$\endgroup\$
    – Ranoiaetep
    Jun 12, 2021 at 6:44
  • 1
    \$\begingroup\$ Some operations are generally more expensive. In this case, I replaced remainder and addition with subtraction. remainder and division are a bit costly, though admittedly the non-locality of list-nodes could easily dominate anyway. \$\endgroup\$ Jun 12, 2021 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.