Problem statement

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

Solution

This is quite classical linked list problem and it is quite nasty in my opinion. It can be a bit problematic to imagine all this in your head, do it on paper. The idea is to add dummy variable, then calculate number of nodes. We need this, because we do not need to reverse last group. Then we use idea similar to problem 0206 Reverse Linked List: but here we need to reverse k elements, and then reconnect first and last nodes in each group and update cnt.

Complexity

Time complexity is O(n), space complexity is O(1).

Code

class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0)
        dummy.next = head
        cur, nxt, pre = dummy, dummy, dummy
        cnt = 0
        while cur.next:
            cnt += 1
            cur = cur.next
            
        while cnt >= k:
            cur = new = pre.next
            nxt = cur.next
            for _ in range(k-1):
                tmp = nxt.next
                nxt.next = cur
                cur = nxt
                nxt = tmp
            
            pre.next = cur
            new.next = nxt
            pre = new
            cnt -= k
            
        return dummy.next