25. Reverse Nodes in k-Group

Hard


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]

 

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

 

Follow-up: Can you solve the problem in O(1) extra memory space?





 # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head, left, right): 
        prev = None
        current = head 

        while left <= right:
            temp = current.next
            current.next = prev 
            prev = current 
            current = temp 
            left+=1

        return prev, head, current

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        if k == 1 or not head:
            return head

        s_head = ListNode(0, head)

        current = s_head
        left, right = 1, 0

        while current.next:
            node = current

            for j in range(k):
                node = node.next
                if not node:
                    break
                right += 1

            if right % k == 0:
                new_head, new_tail, tail_next = self.reverse(current.next, left, right)
                current.next = new_head
                new_tail.next = tail_next
                current = new_tail
                left+=k

            else:
                break



        return s_head.next

Random Note


  1. Effectively Using Django REST Framework Serializers
  2. How To Use DRF Serializers Effectively in Django
  3. My personal django rest framework serializer notes
  4. How to use DRF serializers effectively during write operations