LeetCode 25 - Reverse Nodes in k-Group

Question:

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

Example 1:

Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

Answer:

Creating 2 pointers and reversing the sub-list between them as a simple reverse linked list problem.

Approach:

Given the head of this Single Linked List, and k = 5.

Create a dummy pointer that will point at head, then create 2 pointers back and forward, where back is pointing before the start of the sub-list that will be reversed and forward points at the first node.

forward will iterate until it reaches the next node of the last node from the sub-list that will be reversed.

After that simply reverse the sub-list between back and forward which has length equal to k by calling reverseLinkedList and passing to it the first node of the sub-list which is back->next and passing the end of the sub-list which is the next of the last node in the sub-list which is forward,

The reverseLinkedList will return the first node in the reversed sub-list that will became the next of back, and the next of last node of the sub-list which was the first node before reversing will be the forward.

And back will point where last is pointing at, i.e. back = last.

Apply this operations until the back is nullptr i.e. reaches the end of the list, or forward reaches the end of the list and the sub-list is not of length k i.e. groupLen != k.

Time complexity:

O(n), where n is the number of nodes in the list.

Space complexity:

O(1), since the number of nodes allocated are constant.

Code:

class Solution:
    # @staticMethod
    def reverseLinkedList(self, begin: Optional[ListNode], end: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while begin != end:
            next = begin.next
            begin.next = prev
            prev = begin
            begin = next

        return prev


    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 1 or head is None or head.next is None:
            return head
        
        dummy = ListNode(0, head)
        back, forward = dummy, head

        while back is not None:
            groupLen = 0
            while groupLen < k and forward is not None:
                forward = forward.next
                groupLen += 1
            
            if groupLen != k:
                break
            
            last = back.next

            back.next = self.reverseLinkedList(back.next, forward)
            
            last.next = forward
            back = last

        return dummy.next