Reverse Nodes in k-Group: cái giá của việc đếm trước khi cắt

Bài toán nghe có vẻ gần với "Reverse Linked List" (206). Nhưng không phải. Thành phần thêm vào — chỉ đảo ngược trong từng nhóm đúng k node, để nguyên phần đuôi nếu không đủ — biến một lần duyệt đơn thành một nhịp điệu: đếm, xác nhận, đảo, nối, tiến. Bỏ sót bất kỳ nhịp nào và bạn sẽ làm hỏng list hoặc lật sai phần đuôi.

Constraints cho 1 <= k <= n <= 5000 và giá trị node trong [0, 1000]. Không có gì quá lớn, nhưng follow-up yêu cầu O(1) extra space, loại ngay approach đơn giản nhất. Hãy cùng đi qua cả ba approach mà bài toán gốc đề cập, vì lộ trình từ O(n) xuống O(1) space mới là bài học thực sự ở đây.

Đề bài

Cho head của một linked list, đảo ngược các node theo từng nhóm k node liên tiếp và trả về list đã được chỉnh sửa. Nếu số node còn lại không đủ k, những node đuôi đó phải giữ nguyên thứ tự ban đầu. Chỉ được thay đổi liên kết giữa các node — không được thay đổi giá trị. Full statement: LeetCode 25.

Ràng buộc:
- Số node trong list là n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

Constraints nói gì

n <= 5000 nghĩa là O(n²) vẫn pass, nhưng bài toán này thực sự là O(n) — bạn thăm mỗi node tối đa hai lần (một lần để đếm nhóm, một lần để đảo). Dải giá trị [0, 1000] không liên quan; đây là phẫu thuật pointer thuần túy, giá trị không đóng vai trò gì.

Constraint cấu trúc quan trọng là bạn không được thay đổi giá trị node — chỉ được thay đổi pointer. Điều đó loại bỏ mọi approach dựa trên việc thu thập giá trị, sắp xếp, rồi ghi lại. Bạn phải di chuyển chính các node.

k luôn hợp lệ (k <= n), nên bạn không bao giờ gặp trường hợp toàn bộ list ngắn hơn k. Nhưng partial tail (khi n không chia hết cho k) được đảm bảo xuất hiện khi n % k != 0, và những phần đó phải được giữ nguyên.

Approach 1: thu thập vào array, đảo tại chỗ, nối lại

Cách dịch trực tiếp nhất của bài toán: tạm quên pointer manipulation và chỉ cần di chuyển các node như đối tượng. Thu thập tất cả vào một list, đảo ngược mỗi nhóm k trong list đó bằng two-pointer swapping, rồi nối lại các next pointer để khớp với thứ tự mới.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 1:
            return head
 
        # Thu thập tất cả node vào array
        nodes = []
        current = head
        while current:
            nodes.append(current)
            current = current.next
 
        n = len(nodes)
        # Đảo ngược từng nhóm k hoàn chỉnh tại chỗ
        for i in range(0, n - n % k, k):
            left, right = i, i + k - 1
            while left < right:
                nodes[left], nodes[right] = nodes[right], nodes[left]
                left += 1
                right -= 1
 
        # Nối lại next pointer
        for i in range(n - 1):
            nodes[i].next = nodes[i + 1]
        nodes[n - 1].next = None
 
        return nodes[0]

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
 
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
 
        var nodes = new List<ListNode>();
        ListNode current = head;
        while (current != null) {
            nodes.Add(current);
            current = current.next;
        }
 
        int n = nodes.Count;
        for (int i = 0; i <= n - k; i += k) {
            int left = i, right = i + k - 1;
            while (left < right) {
                ListNode temp = nodes[left];
                nodes[left] = nodes[right];
                nodes[right] = temp;
                left++;
                right--;
            }
        }
 
        for (int i = 0; i < n - 1; i++) {
            nodes[i].next = nodes[i + 1];
        }
        nodes[n - 1].next = null;
 
        return nodes[0];
    }
}

Bound của vòng lặp range(0, n - n % k, k) / i <= n - k là chi tiết then chốt. n - n % k là index của phần tử cuối cùng trong nhóm hoàn chỉnh cuối. Nếu n = 5 và k = 3, thì n % k = 2, nên chúng ta chỉ xử lý index 0..2. Index 3..4 giữ nguyên thứ tự tương đối vì không bao giờ bị swap.

Complexity: Time O(n) — một lần duyệt để thu thập, O(n) để swap, O(n) để nối lại. Space O(n) cho array. Đây là approach mà follow-up yêu cầu bạn phải cải thiện.

Approach 2: iterative in-place — giải pháp O(1) space

Đây là approach tôi sẽ ship. Ý tưởng là làm việc từng nhóm một mà không cần materialization: tìm node thứ k phía trước (để xác nhận độ đầy đủ của nhóm), đảo ngược k node giữa group_prev và kth_node, rồi nối biên giới và tiến lên.

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        group_prev = dummy
 
        while True:
            kth_node = self._get_kth(group_prev, k)
            if not kth_node:
                break
 
            group_next = kth_node.next
 
            # Đảo ngược nhóm: prev bắt đầu tại group_next (neo đuôi)
            prev, curr = kth_node.next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
 
            # Nối: group_prev -> kth_node (head mới của nhóm đã đảo)
            #       head cũ của nhóm (nay là đuôi) -> group_next
            tmp = group_prev.next          # head cũ của nhóm, nay là đuôi
            group_prev.next = kth_node     # nối với head mới của nhóm đã đảo
            group_prev = tmp               # tiến group_prev đến đuôi mới
 
        return dummy.next
 
    def _get_kth(self, node: ListNode, k: int) -> ListNode:
        while node and k > 0:
            node = node.next
            k -= 1
        return node

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;
 
        while (true) {
            ListNode kthNode = GetKth(groupPrev, k);
            if (kthNode == null) break;
 
            ListNode groupNext = kthNode.next;
 
            ListNode prev = kthNode.next;
            ListNode curr = groupPrev.next;
 
            while (curr != groupNext) {
                ListNode nxt = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nxt;
            }
 
            ListNode tmp = groupPrev.next;
            groupPrev.next = kthNode;
            groupPrev = tmp;
        }
 
        return dummy.next;
    }
 
    private ListNode GetKth(ListNode node, int k) {
        while (node != null && k > 0) {
            node = node.next;
            k--;
        }
        return node;
    }
}

Trace tay: [1, 2, 3, 4, 5], k = 3

Hãy bước qua nhóm đầu tiên một cách chính xác. Dummy node ở vị trí 0, nên group_prev = dummy.

Iteration 1:

_get_kth(dummy, 3) đi qua: dummy -> 1 -> 2 -> 3, trả về node 3. Đó là kth_node.

group_next = node(4).

Đảo từ node(1) đến node(3) với prev = node(4) làm neo đuôi:

prev=4, curr=1:  1.next = 4,  prev=1, curr=2
prev=1, curr=2:  2.next = 1,  prev=2, curr=3
prev=2, curr=3:  3.next = 2,  prev=3, curr=4  (curr == group_next, dừng)

Sau vòng lặp trong, prev = node(3) là head mới của nhóm đã đảo. Chuỗi là 3 -> 2 -> 1 -> 4 -> 5.

Nối: tmp = dummy.next (vẫn là node(1) lúc này — head cũ, nay là đuôi). dummy.next = node(3). group_prev = node(1).

List hiện tại: dummy -> 3 -> 2 -> 1 -> 4 -> 5 -> null, với group_prev tại node(1).

Iteration 2:

_get_kth(node(1), 3) đi qua: 1 -> 4 -> 5 -> null. Trả về null vì chỉ còn 2 node sau node(1). Vòng lặp dừng.

Kết quả cuối: [3, 2, 1, 4, 5]. Đúng.

Logic stitching là phần mọi người hay làm sai. tmp = group_prev.next phải được capture trước khi group_prev.next = kth_node ghi đè nó. Chỉ một dòng thứ tự đó là nơi hầu hết các implementation thất bại.

Complexity: Time O(n) — mỗi node được thăm tối đa hai lần: một lần trong lần probe kth-node, một lần trong reversal. Space O(1) — ba pointer, không có cấu trúc bổ sung.

Approach 3: recursion — thanh lịch nhưng chú ý stack

Công thức đệ quy là ngắn nhất để viết và dễ xác minh nhất khi nhìn lướt qua.

Base case: nếu còn lại ít hơn k node, trả về head không thay đổi.

Recursive case: đếm tiến k bước để xác nhận độ đầy đủ nhóm, sau đó recurse trên phần còn lại trước (depth-first), rồi đảo nhóm hiện tại với đuôi của nó trỏ vào kết quả của recursive call.

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        curr = head
        count = 0
        while curr and count < k:
            curr = curr.next
            count += 1
 
        if count < k:
            return head
 
        # curr bây giờ trỏ đến head của nhóm tiếp theo
        # Recurse trước, rồi đảo nhóm hiện tại xung quanh kết quả
        rest = self.reverseKGroup(curr, k)
 
        prev = rest
        curr = head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
 
        return prev

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }
 
        if (count < k) return head;
 
        ListNode rest = ReverseKGroup(curr, k);
 
        ListNode prev = rest;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
 
        return prev;
    }
}

Insight then chốt: bằng cách recurse trước và đảo ngược sau, head ban đầu của nhóm hiện tại (nay là đuôi sau khi đảo) có thể được gán trực tiếp curr = rest — nó tự nhiên trở thành connector đến nhóm đã đảo tiếp theo.

Complexity: Time O(n) — mỗi node được thăm một lần ở mỗi cấp của recursion và tổng công việc qua tất cả các cấp là O(n). Space O(n/k) — độ sâu recursion chính xác là floor(n/k), số nhóm hoàn chỉnh. Trong trường hợp xấu nhất (k = 1), đó là O(n) stack frame.

Mối lo ngại về độ sâu stack với k = 1 có phần lý thuyết trong bài toán này vì constraints cho k <= n <= 5000, nhưng trong Python nơi giới hạn recursion mặc định là 1000, một list gồm 5000 node với k = 1 thực sự sẽ chạm giới hạn. Đây là bug thực tế, không phải lý thuyết.

Các edge case quan trọng

k = 1: Không cần đảo ngược. Giải pháp iterative kết thúc đúng vì _get_kth trả về node đầu tiên, vòng lặp reversal chạy một lần (no-op vì prev = group_next), và tiến đúng. Giải pháp đệ quy trả về head sau khi recurse trên curr là head.next — về cơ bản rebuild lại list không thay đổi. Giải pháp array swap từng nhóm một phần tử, không thay đổi gì.

Đuôi ngắn hơn k: Đây là hành vi định nghĩa của bài toán. Giải pháp iterative kiểm tra _get_kth trả về None; bound vòng lặp của array loại trừ partial tail; giải pháp đệ quy trả về head khi count < k. Cả ba xử lý đúng nhưng qua các cơ chế khác nhau — approach array có thể nói là rõ ràng nhất.

n == k (toàn bộ list là một nhóm): Cả ba approach đảo ngược toàn bộ list. Không có phần đuôi thừa. Đáng test riêng để xác nhận logic stitching đặt tail.next = null thay vì để lại dangling pointer.

n chia hết cho k: Tất cả nhóm đều hoàn chỉnh, không có đuôi. Vòng lặp iterative kết thúc khi _get_kth trả về None ở cuối cùng. Recursion kết thúc khi nhóm cuối cùng thấy không còn node nào. Cả hai đều sạch.

Node đơn (n = 1, k = 1): Trivial — không đảo ngược. Cả ba approach trả về input không thay đổi. Kỹ thuật dummy node trong giải pháp iterative tồn tại chính xác để tránh phải xử lý đặc biệt head.

Bảng so sánh

Cả ba đều O(n) time. Câu chuyện về space là điều phân biệt chúng.

Tôi sẽ ship cái gì, và tại sao

Iterative, không do dự. Đảm bảo O(1) space được nêu rõ trong follow-up, nhưng quan trọng hơn là phiên bản iterative không có failure mode ẩn — không có recursion limit, không có implicit stack, không phụ thuộc vào độ sâu call có thể đạt bao nhiêu. Logic stitching (tmp = group_prev.next; group_prev.next = kth_node; group_prev = tmp) trông phức tạp khi đọc lần đầu nhưng quy về: lưu head cũ, nối đuôi trước đó với head mới, tiến con trỏ đuôi trước đó lên. Khi bạn trace qua một lần với ví dụ cụ thể, nó khắc vào trí nhớ.

Phiên bản đệ quy thì đẹp và tôi sẽ không reject nó trong code review. Nhưng trong production code nơi list có thể dài tùy ý, tôi không muốn phải giải thích tại sao case k = 1 lại crash với recursion error.

Phiên bản array tồn tại để giải thích tại sao bạn cần gì đó tốt hơn. Đừng bao giờ ship nó.

Pattern có thể chuyển giao: group-chunked in-place pointer manipulation

Bài toán này thuộc một họ bài toán nơi bạn xử lý linked list trong các cửa sổ kích thước cố định, áp dụng một số phép biến đổi bên trong mỗi cửa sổ và cẩn thận nối biên giới cửa sổ. Kỹ năng cốt lõi là duy trì bốn điểm tham chiếu đồng thời: node trước nhóm (group_prev), node đầu tiên của nhóm (đuôi tương lai), node cuối cùng của nhóm (head tương lai), và node đầu tiên của nhóm tiếp theo. Mất dấu bất kỳ một trong bốn cái này là làm hỏng list.

Cùng kỷ luật bốn pointer đó xuất hiện trong các bài toán phân tách và hợp nhất các đoạn list, xoay list theo một lượng cố định, hay phân vùng list quanh một pivot — phép toán cụ thể bên trong mỗi nhóm thay đổi, nhưng quản lý biên giới vẫn giống hệt.

Vị trí trong series linked list

Bài toán này đến sau Reverse Linked List (206), bài đã thiết lập kỹ thuật reversal ba pointer, và sau Reorder List (143), bài yêu cầu tách và đan xen. Reverse Nodes in k-Group là bước leo thang: thay vì đảo ngược toàn bộ list hay một lần split cố định, bạn tham số hóa kích thước reversal và phải xử lý partial tail.

Swap Nodes in Pairs (24) là trường hợp đặc biệt k = 2. Nếu bài này cảm thấy thoải mái, hãy quay lại đọc 24 — bạn sẽ nhận ra giải pháp iterative giống hệt nhau với k được hardcode là 2, và giải pháp đệ quy là một base case và một recursive call với pair-swap được inline.

Reverse Linked List II (92) là biến thể nhóm đơn: đảo ngược chính xác các node giữa vị trí left và right. Bài toán stitching biên giới giống nhau; bạn chỉ làm nó một lần thay vì lặp đi lặp lại.

Rotate List (61) là group processing không có reversal. Bạn tìm đuôi mới ở vị trí n - k % n, cắt ở đó, và nối lại head. Helper "tìm node thứ k từ cuối" bạn cần về cơ bản là _get_kth cải trang.

Split Linked List in Parts (725) tổng quát hóa thành các nhóm không đều: phân phối n node thành k phần đồng đều nhất có thể, với các phần trước được thêm một node khi không chia hết. Logic đếm phức tạp hơn, nhưng quản lý biên giới đoạn là cùng pattern.