You are given the head of a linked list and an integer k.
Your task is to reverse the nodes of the list k at a time, and return the modified list.

If the number of nodes remaining at the end is less than k, leave them as-is.

---

Understanding the Problem

Example:

Input: 1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5

Explanation:
First pair reversed: 2,1
Next pair reversed: 4,3
Remaining 5 is alone, so it stays.

Another example:

Input: 1 → 2 → 3 → 4 → 5, k = 3
Output: 3 → 2 → 1 → 4 → 5

Explanation:
First group of 3 reversed: 3,2,1
Remaining nodes (4,5) < 3, so no reversal.

---

Approach (Explained in Simple Language)

This problem requires chunk-based reversal of the linked list.

1. Use a dummy node

Simplifies handling head changes.

2. Check if at least k nodes remain

If fewer than k nodes remain, stop and return the list.

3. Reverse the next k nodes

Typical linked-list reversal, but only for k steps.

4. Connect the reversed segment

Keep track of:
the node before the group
the first node of the group (which becomes the last after reversal)
the node after the group

5. Move to next k-group

Repeat until no more full groups exist.

This approach ensures the entire list is processed in linear time.

---

Java Code

class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {

        if (head == null || k == 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode groupPrev = dummy;

        while (true) {

            ListNode kth = getKthNode(groupPrev, k);
            if (kth == null) {
                break;
            }

            ListNode groupNext = kth.next;

            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;

            while (curr != groupNext) {
                ListNode temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
            }

            ListNode temp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = temp;
        }

        return dummy.next;
    }

    private ListNode getKthNode(ListNode start, int k) {
        while (start != null && k > 0) {
            start = start.next;
            k--;
        }
        return start;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

---

Dry Run

Input:
1 → 2 → 3 → 4 → 5
k = 2

Let’s walk step by step.

dummy → 1 → 2 → 3 → 4 → 5
groupPrev = dummy

---

Step 1: Find kth node

getKthNode(dummy, 2) → node with value 2
kth = 2
groupNext = 3

We will reverse nodes between groupPrev.next (1) and kth (2).

---

Reverse nodes 1 and 2

Initial:
prev = 3
curr = 1

Iteration 1:
temp = 2
1.next = 3
prev = 1
curr = 2

Iteration 2:
temp = 3
2.next = 1
prev = 2
curr = 3

Reversed segment:
2 → 1 → 3

Connect:

groupPrev.next = kth → 2
groupPrev becomes old start of segment → 1

List becomes:
dummy → 2 → 1 → 3 → 4 → 5
groupPrev = 1

---

Step 2: Find next kth node

getKthNode(1, 2) → node with value 4
kth = 4
groupNext = 5

Reverse nodes 3 and 4.

prev = 5
curr = 3

Iteration 1:
temp = 4
3.next = 5
prev = 3
curr = 4

Iteration 2:
temp = 5
4.next = 3
prev = 4
curr = 5

Reversed segment:
4 → 3 → 5

Connect:

groupPrev.next = 4
groupPrev = 3

List becomes:
2 → 1 → 4 → 3 → 5

---

Step 3: Attempt next kth node

getKthNode(3, 2) → returns null (only one node left)

Stop.

---

Final Output

2 → 1 → 4 → 3 → 5

---

Why This Approach Works

By splitting the list into groups of k and reversing each independently, while always keeping track of:

the node before the group
the k-th node
the head and tail of the reversed portion

we can efficiently reverse each segment without disrupting the rest of the list.

The algorithm runs in:

Time: O(n) because each node is reversed once
Space: O(1) because no extra data structure is used