hardLinked List

Reverse Nodes in k-Group

Reverse linked-list nodes in groups of k. Leave the final group unchanged if it has fewer than k nodes.

LeetCode ↗

Work through the cases

3 examples

Input notation

List values on line 1; positive k on line 2.

Expected result

The reordered values.

Case 1

Input

1 2 3 4 5
2

Expected output

2 1 4 3 5

Case 2

Input

1 2 3 4
3

Expected output

3 2 1 4

Case 3

Input

1 2 3
1

Expected output

1 2 3

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is recursion by groups: reverse k nodes, then recurse on the rest. n ≤ 5000 would pass, but the follow-up asks for O(1) extra space, and a recursive stack grows with the number of groups. Two places are easy to get wrong: we must confirm a full group of k (otherwise leave the tail alone), and we must splice the reversed segment back without dropping a pointer. Inside a group the work is ordinary list reversal; between groups we only need the previous tail. Start from a dummy, walk k steps to probe, then detach, reverse, and reconnect; stop when a probe falls short. Probe, reverse, and relink are all pointer writes, so extra space is O(1).

We can simulate the entire reversal process according to the problem description.

First, we define a helper function reverse to reverse a linked list. Then, we define a dummy head node dummy and set its next pointer to head.

Next, we traverse the linked list, processing k nodes at a time. If the remaining nodes are fewer than k, we do not perform the reversal. Otherwise, we extract k nodes and call the reverse function to reverse these k nodes. Then, we connect the reversed linked list back to the original linked list. We continue to process the next k nodes until the entire linked list is traversed.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre != null) {
            ListNode cur = pre;
            for (int i = 0; i < k; i++) {
                cur = cur.next;
                if (cur == null) {
                    return dummy.next;
                }
            }
            ListNode node = pre.next;
            ListNode nxt = cur.next;
            cur.next = null;
            pre.next = reverse(node);
            node.next = nxt;
            pre = node;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = nxt;
        }
        return dummy.next;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.