Skip to content

25. Reverse Nodes In K Group

Linked List Recursion

Problem - 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?

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
            pointer = ListNode(0)
            current = head
            while current:
                next_node = current.next
                current.next = pointer.next
                pointer.next = current
                current = next_node
            return pointer.next

        pointer = previous = ListNode(0, head)
        while previous:
            current = previous
            for i in range (k):
                current = current.next
                if current is None:
                    return pointer.next
            node = previous.next
            next_node = current.next
            current.next = None
            previous.next = reverse(node)
            node.next = next_node
            previous = node

        return pointer.next

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 18.5 MB (58.77%)