Problem

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.

Examples

Example 1:

---
title: head = [1, 2, 3, 4, 5], k = 2
---
graph LR;
	1:::or --> 2:::or --> 3:::gr --> 4:::gr --> 5

classDef or fill:#FFB870
classDef gr fill:#89C484
  
---
title: Output
---
graph LR;
	2:::or --> 1:::or --> 4:::gr --> 3:::gr --> 5

classDef or fill:#FFB870
classDef gr fill:#89C484
  
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [3, 2, 1, 6, 5, 4, 9, 8, 7, 10, 11], k = 3
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

---
title: Input Linked List, K = 3
---
graph LR;
	3:::or --> 2:::or --> 1:::or --> 6 --> 5 --> 4 --> 9:::gr --> 8:::gr --> 7:::gr --> 10:::bl --> 11:::bl

classDef or fill:#FFB870
classDef gr fill:#89C484
classDef bl fill:#9999CC
  
---
title: Output Linked List
---
graph LR;
	1:::or --> 2:::or --> 3:::or --> 4 --> 5 --> 6 --> 7:::gr --> 8:::gr --> 9:::gr --> 10:::bl --> 11:::bl

classDef or fill:#FFB870
classDef gr fill:#89C484
classDef bl fill:#9999CC

The following are the sequence of steps to be followed. In this solution, we will be using the reverse of a linked list solution described here: Reverse Linked List Problem.

Solution

Method 1 - Recursive

Code

Java
 public ListNode reverseKGroup(ListNode head, int k) {
    //1. test weather we have more then k node left, if less then k node left we just return head 
    ListNode node = head;
    int count = 0;
    while (count < k) { 
        if(node == null)return head;
        node = node.next;
        count++;
    }
    // 2.reverse k node at current level 
       ListNode pre = reverseKGroup(node, k); //pre node point to the the answer of sub-problem 
        while (count > 0) {  
            ListNode next = head.next; 
            head.next = pre; 
            pre = head; 
            head = next;
            count = count - 1;
        }
        return pre;
}

Method 2 - Iterative

Here are the steps we can take:

  • HeaderNode is the head of the linked list
  • Take three pointers StartNode, EndNode and NextNode
  • Let the NextNode pointer points to HeaderNode and unlink HeaderNode
  • Repeat the following steps until NextNode is null
    • Point StartNode and EndNode to NextNode
    • Move EndNode K nodes away from StartNode
    • Point NextNode to the node next to EndNode
    • Unlink EndNode from the linked list
    • Now reverse the list pointed by StartNode which gives reverse of K nodes
    • If HeaderNode is null point the HeaderNode to reversed list else point the reversed list to the end of the HeaderNode list
  • Hence the list pointed by HeaderNode contains the K- Reverse of a linked list

Consider the following linked list where headerNode is pointing to head of the linked list:

%% TODO: add diagram

Dry run for the above example: For k=3: Step 1: Initially headerNode, startNode and endNode point to null and nextNode points to head of the list.

Step 2: In the loop beginning, startNode and endNode points to nextNode.

Step 3: Now endNode  points to the node which is K nodes away from startNode. As K=3, startNode points to 1 and endNode points to 3.

Step 4: Save nextNode point to the next node of the endNode so that we can begin the next iteration from nextNode

Step 5: Now unlink the endNode from the list. And pass the list pointed by startNode to the reverse function

Step 6: The reversal of the list pointed by startNode is returned as 3 -> 2 -> 1

Step 7: As the headerNode is null, point startNode to headerNode and repeat the loop. Now the loop is repeated for the rest of the linked list. And the list pointed by startNode gets reversed.

Step 8: As the headerNode is not null, the last element of the current headerNode list gets linked to the list pointed by startNode

As the nextNode is pointing to null, the while loop ends. %%

Code

Java
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }
        // Dummy node to simplify handling of the list head
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // Initialize pointers
        ListNode prevGroupEnd = dummy;
        // Iterate through the list in segments of k nodes
        while (true) {
            ListNode groupStart = prevGroupEnd.next;
            ListNode groupEnd = prevGroupEnd;

            // move group end k nodes ahead
            for (int i = 0; i < k && groupEnd != null; i++) {
                groupEnd = groupEnd.next;
            }

            if (groupEnd == null) {
                break; // fewer than k nodes, hence we are done
            }

            ListNode nextGroupStart = groupEnd.next;
            // Reverse the current k-group
            ListNode prev = nextGroupStart,
            curr = groupStart,
            next = null;
            while (curr != nextGroupStart) {
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }


            prevGroupEnd.next = groupEnd;
            prevGroupEnd = groupStart;
        }

        return dummy.next;
    }
}