Technical Interview Question

You are given a linked list and an integer k. Your task is to reverse every k nodes in 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.

For example, given the linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 3, you should return 3 -> 2 -> 1 -> 4 -> 5.

Write a function reverseKGroup(head, k) to solve this problem, where head is the head of the linked list and k is the size of the group for reversal.

Note:

• The linked list is guaranteed to be valid and can be modified in-place.
• You may not alter the values in the nodes, only nodes itself may be changed.
• Only constant memory is allowed (for example, you cannot construct a new list and use additional memory).

Example

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 3

Output: 3 -> 2 -> 1 -> 4 -> 5

Answer

To solve this problem, we can use a recursive approach to reverse each group of nodes of size k. Here is the step-by-step detailed explanation of the solution:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

First, we need to define a helper function to reverse a group of k nodes:

def reverseKNodes(prev, head, k):
    current = head
    next_node = None
    count = 0

    # Check if there are enough nodes to reverse
    while count < k and current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
        count += 1

    # If the number of nodes is less than k, then revert the reversed part
    if count < k: 
        return reverseKNodes(None, prev, count)

    # If there are more nodes, reverse the next set of k nodes
    if next_node is not None:
        head.next = reverseKNodes(None, next_node, k)
    
    return prev

Now, we can use the reverseKGroup function to handle the starting point and call the helper function:

def reverseKGroup(head, k):
    # Create a dummy node and set its next to the head of the list
    dummy = ListNode(0)
    dummy.next = head

    # Initialize previous node as the dummy
    prev = dummy
    while True:
        # Set the head of the next k-group
        head = prev.next

        # Get the kth node in the group
        tail = prev
        for _ in range(k):
            tail = tail.next
            if tail is None:
                return dummy.next

        # Reverse the current k-group of nodes
        prev.next = reverseKNodes(None, head, k)
        head.next = tail

        # Move the pointers for the next iteration
        prev = head
    
    return dummy.next

This solution uses the iterative approach with a constant space complexity O(1) and a time complexity of O(n), where n is the number of nodes in the linked list. The reverseKGroup function reverses each group of k nodes in the linked list.

Let's test the solution with the given example:

# Create the linked list 1 -> 2 -> 3 -> 4 -> 5
n5 = ListNode(5)
n4 = ListNode(4, n5)
n3 = ListNode(3, n4)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)

# Test reverseKGroup function with k = 3
result = reverseKGroup(n1, 3)

# Verify the output
while result:
    print(result.value)
    result = result.next

The output should be:

3
2
1
4
5

This indicates that the reverseKGroup function has successfully reversed the nodes in groups of k (i.e., 3 in this case).