Reverse Nodes in k-Group - Python Solution

1. Introduction

"Reverse Nodes in k-Group" is a more complex linked list problem that involves reversing portions of a list in segments of a specified size. This problem is a step up from basic linked list reversal, requiring more intricate manipulation of node pointers. It is often used to test a deeper understanding of linked list operations in algorithm design.

Problem

Given the head of a linked list, the task is to 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, the remaining nodes at the end should stay in their original order. Node values must not be altered, only the nodes themselves may be changed.

2. Solution Steps

1. Write a helper function to reverse a segment of the list.

2. Initialize pointers to manage the current segment and its previous and next segments.

3. Iterate through the list, reversing segments of size k.

4. After reversing a segment, reconnect it with the previous and next segments.

5. Handle edge cases where the list's length is not a multiple of k.

6. Return the new head of the list, which may be different from the original head if k is not 1.

3. Code Program

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

def reverseKGroup(head, k):
    def reverse(head, tail):
        prev, curr = None, head
        while prev != tail:
            next_temp = curr.next
            curr.next = prev
            prev, curr = curr, next_temp
        return prev

    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head:
        tail = prev
        for i in range(k):
            tail = tail.next
            if not tail:
                return dummy.next

        next_segment = tail.next
        head, tail = reverse(head, tail)
        prev.next = head
        tail.next = next_segment

        head = next_segment
        prev = tail

    return dummy.next

# Example Usage
# Creating list for demonstration: [1 -> 2 -> 3 -> 4 -> 5]
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = reverseKGroup(head, 2)
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[2, 1, 4, 3, 5]

Explanation:

1. ListNode Class: ListNode class is used for representing each node in the linked list.

2. Reversal Function: A helper function reverse is defined to reverse a segment of the list.

3. Dummy Node: A dummy node simplifies the process of handling the head of the list.

4. Segment Management: The list is processed in segments of size k, reversing each segment using the reverse function.

5. Reconnection: After reversing, each segment is reconnected to the rest of the list.

6. Edge Cases: The function handles cases where the number of nodes is not a multiple of k.

7. Result: The function returns the head of the modified list with nodes reversed in k-size groups.