LeetCode problem #25–Reverse nodes in k-group (JavaScript)

In this LeetCode challenge, we’re asked to reverse the elements of a LinkedList, in a very similar way to in the previous challenge. What’s different this time however, is that the number of nodes in each batch to be reversed is determined at run-time, instead of being a standard 2.

To give an example, given a LinkedList with values of [1, 2, 3, 4, 5, 6] , we previously reversed all pairs to get [2, 1, 4, 3, 6, 5] . Now however, we might be passed reverse-group-size value (k) of 3, which would cause the LinkedList to become [3, 2, 1, 6, 5, 4] , or 4, which would create [4, 3, 2, 1, 5, 6] (because there aren’t enough nodes to reverse the 2nd set of 4 nodes).

To help understand the below solutions, we will split this problem into two parts.

The first part is to identify blocks of ListNodes that need reversing. If we have 5 nodes in our LinkedList, and have been given a k value of 2, then we know we can reverse the nodes [1, 2] (to get [2, 1]), and [3, 4] (to get [4, 3]), but 5 will be left as is, giving us a final output of [2, 1, 4, 3, 5]. Likewise, if we’re given a k of 4, then we must reverse [1, 2, 3, 4] (to get [4, 3, 2, 1]) but do not have enough nodes for a second batch of reversal, so we’re left with [4, 3, 2, 1, 5].

The second part is the actual reversal. In order to reverse a LinkedList, we’ll need to point each ListNode to its predecessor, and then point the final node to the node that follows. Back To Back SWE did a great video on this that I’d recommend watching, as its a difficult concept to explain here.

Solution #1: Recursive

LeetCode user schpolsky posted this very elegant recursive solution to the problem. In it, we reverse the first k elements of the passed in LinkedList, and call the function again on the rest of the LinkedList. If the rest of the LinkedList is k or more elements long, another reversal is carried out on that segment, and the process continues. If not, the last part of the LinkedList is returning in its original order, and the overall LinkedList is then returned.

Solution #2: Iterative

LeetCode user ofLucas posted this great iterative solution (ironically enough, n the comments to the other recursive solution!). It first establishes the total length of the LinkedList, and then loops through the initial LinkedList, keeping track of the starting point of the current batch of k nodes, and then reverses them if it reaches k nodes in size. This process repeats until the loop runs out of elements, by which point we have reversed every batch of k nodes in the LinkedList.