Problem Statement

Given a singly linked list and an integer k, reverse the nodes of the list k at a time and return the modified list. Nodes that are not in groups of k should remain in their original order.

Examples

Example 1:

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

Explanation: The groups 1->2 and 3->4 were reversed as 2->1 and 4->3

Example 2:

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

Explanation: The groups 1->2->3 were reversed as 3->2->1.
Note that 4->5 is not reversed, as it does not form the group of k = 3.

Approaches

Intuition:

The intuition is to reverse the nodes of the linked list in groups of k by identifying each group, reversing the links within that group, and then connecting the reversed groups, leaving any remaining nodes as they are if the group is less than k.

Approach:

First, traverse the linked list to identify segments of K nodes. For each segment, adjust the pointers within the segment to reverse the direction of the nodes. This involves iterating through the segment and changing the links between nodes.

Next, after reversing a segment, connect the reversed segment to the previous part of the list. Continue this process until you reach the end of the list.

Finally, if there are fewer than K nodes left at the end of the list, leave them as they are. Return the head of the modified linked list.

Below is the algorithm for the approach:-

• Initialize a pointer temp to the head of the linked list. Using temp, traverse to the Kth node iteratively.
• Upon reaching the Kth node, preserve the Kth node’s next node as nextNode and set the Kth node’s next pointer to null. This effectively breaks the linked list into a smaller list of size K that can be reversed and attached back.
• Treat this segment from temp to the Kth node as an individual linked list and reverse it. This can be done using a helper function that reverses the linked list.
• The reversed linked list segment returns a modified list with temp now at its tail and the Kth node pointing to its head. Update temp's next pointer to nextNode. If reversing the first segment of K nodes, update the head to the Kth node.
• Continue this reversal process for further groups. If a segment has fewer than K nodes, leave them unmodified and return the new head. Use the prevLast pointer to maintain the link between the end of the previous reversed segment and the current segment.