Reverse Linked List: ba con trỏ và tại sao thứ tự quan trọng

Linked list không có chỉ số. Bạn không thể nhảy thẳng đến node i mà phải đi từ head, từng bước .next một. Ràng buộc duy nhất đó — con đường duy nhất về phía trước là qua .next — có nghĩa là đảo ngược danh sách hoàn toàn xoay quanh chuyện ai đang giữ .next ở mỗi bước. Lật nó để trỏ ngược lại. Tiến về phía trước. Lặp lại. Cái nguy hiểm ở đây là lật .next của node hiện tại ngay lập tức cắt đứt đường đến phần còn lại của danh sách. Vậy nên bạn phải lưu đường đó trước. Đó là toàn bộ thuật toán.

Constraints và những gì chúng thực sự buộc bạn làm

Danh sách có tối đa 5000 node và giá trị trong [-5000, 5000]. Khoảng giá trị không liên quan gì — chúng ta không so sánh giá trị, chỉ nối lại pointer. Số node đủ nhỏ để cả iterative O(1) space lẫn recursive O(n) space đều khả thi về mặt kỹ thuật.

Nhưng 5000 node cũng chính xác là nơi recursion limit mặc định 1000 frame của Python trở thành vấn đề thực tế với cách recursive. Sự bất đối xứng đó quan trọng: hai giải pháp có O(n) time giống nhau nhưng rủi ro vận hành khác nhau hoàn toàn. Constraint không loại trừ recursion — nó chỉ làm cho việc lựa chọn không còn đơn giản nữa.

Danh sách cũng có thể rỗng. head = null là input hợp lệ và phải cho ra output null, không phải crash. Cả hai cách tiếp cận đều không cần nhánh xử lý đặc biệt cho trường hợp này — nó tự nhiên xử lý được.

Hình dạng ban đầu của bài toán

Trước khi đụng vào code, đây là [1, 2, 3, 4, 5] trông như thế nào, và chúng ta cần đến đâu:

Mọi mũi tên trỏ phải đều cần trỏ trái. Cấu trúc node không thay đổi — chỉ .next thay đổi trên mỗi node.

Tại sao thứ tự operations là phần khó

Khởi tạo ba con trỏ: prev = None, curr = head. Biến thứ ba, next_node, dùng bên trong vòng lặp. Mỗi bước cần làm:

1. Lưu curr.next trước khi đụng vào nó.
2. Lật curr.next để trỏ về prev.
3. Tiến prev đến curr.
4. Tiến curr đến next_node vừa lưu.

Nếu làm bước 2 trước bước 1, bạn vừa cô lập toàn bộ phần từ curr.next trở đi. Không còn pointer nào trỏ vào phần đó của danh sách, và nó biến mất. Lưu trước. Luôn luôn.

Đây là trạng thái pointer sau mỗi vòng lặp qua [1, 2, 3, 4, 5]:

Giải pháp iterative: O(n) time, O(1) space

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr is not None:
            next_node = curr.next   # lưu trước khi ghi đè
            curr.next = prev        # lật link
            prev = curr             # tiến prev
            curr = next_node        # tiến curr
        return prev

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;  // lưu trước khi ghi đè
            curr.next = prev;               // lật link
            prev = curr;                    // tiến prev
            curr = nextNode;                // tiến curr
        }
        return prev;
    }
}

Đây là version tôi sẽ dùng để ship. O(1) space, không rủi ro stack, dễ đọc lại trong code review sáu tháng sau.

Giải pháp recursive: O(n) time, O(n) space

Cách recursive đáng học vì nó xuất hiện trong các bài khó hơn. Reverse Nodes in k-Group (25) xây dựng trên nền tảng này. Logic: recursion xuống tận tail, rồi sửa link trên đường quay về.

Base case: nếu head là None hoặc head.next là None, trả về head. Một node đơn đã là danh sách đảo ngược rồi.

Recursive case: gọi reverseList(head.next) và để nó trả về head mới của sublist đã được đảo ngược. Lúc này head.next vẫn trỏ vào node đang đứng ở tail của suffix đã đảo. Làm cho tail node đó có .next trỏ ngược về head, rồi đặt head.next = None để kết thúc danh sách. Trả về head mới — giá trị này không thay đổi trong suốt quá trình recursion.

Cây recursion cho [1, 2, 3] trước khi unwind:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head   # node thứ hai cũ giờ trỏ ngược lại
        head.next = None        # head trở thành tail mới
        return new_head

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = ReverseList(head.next);
        head.next.next = head;  // node thứ hai cũ giờ trỏ ngược lại
        head.next = null;       // head trở thành tail mới
        return newHead;
    }
}

Dòng head.next.next = head hay gây nhầm lẫn. Trước khi lời gọi recursion trả về, head.next vẫn trỏ vào node cũ thứ hai — node đang đứng ở tail của suffix đã đảo. Vậy head.next.next là field .next của tail, hiện đang là None. Bạn đặt nó thành head. Sau đó đặt head.next = None để cắt đứt link forward cũ. Không có dòng thứ hai, bạn tạo ra một cycle: head.next vẫn trỏ về phía trước, và head.next.next giờ trỏ ngược về head.

Trace từng bước khi unwind [1, 2, 3]:

• reverseList(3) là base case — trả về 3.
• Quay về reverseList(2): new_head = 3, 2.next.next = 2 tức 3.next = 2, rồi 2.next = None. Danh sách là 3 -> 2 -> None. Trả về 3.
• Quay về reverseList(1): new_head = 3, 1.next.next = 1 tức 2.next = 1, rồi 1.next = None. Danh sách là 3 -> 2 -> 1 -> None. Trả về 3.

So sánh hai cách tiếp cận

Cả hai đều chạm vào mỗi node một lần — time complexity giống nhau. Sự khác biệt về space không chỉ là lý thuyết. Với 5000 node, cách recursive xây 5000 call frame. Trong Python điều đó vượt recursion limit mặc định và raise RecursionError trừ khi bạn gọi sys.setrecursionlimit(6000) trước. Trong C# stack sâu hơn và sống qua được, nhưng vẫn đang dùng O(n) memory mà không có lý do thuật toán nào. Tôi chỉ dùng cách recursive nếu bài đặc biệt yêu cầu recursion hoặc khi tôi đang nghiên cứu logic của k-group reversal.

Các edge case, từng cái một

Danh sách rỗng (head = None): Vòng lặp iterative không bao giờ chạy. prev là None từ khởi tạo. Trả về None. Với recursive: check if not head bắt luôn, trả về head (là None). Cả hai xử lý không cần nhánh đặc biệt.

Một node: Iterative chạy một lần. next_node = None. curr.next = None (vốn đã vậy). prev = curr. curr = None. Trả về prev. Đúng — một node đơn là đảo ngược của chính nó. Recursive: not head.next là true, trả về head ngay lập tức.

Hai node (1 -> 2 -> None): Iterative chạy hai lần. Sau vòng 1: None <- 1, curr=2. Sau vòng 2: None <- 1 <- 2, curr=None. Trả về 2. Đây là trường hợp nhỏ nhất không tầm thường, đáng trace tay một lần.

Danh sách đạt giới hạn tối đa (5000 node): Iterative xử lý trong O(n) time, O(1) space, không vấn đề gì. Recursive sẽ chạm Python stack limit ở 1000 frame — hoặc tăng sys.setrecursionlimit hoặc dùng iterative.

Tất cả node có giá trị giống nhau: Giá trị không liên quan — thuật toán chỉ đụng vào pointer .next. Danh sách 5000 node toàn giá trị 0 đảo ngược y hệt danh sách với giá trị khác nhau hoàn toàn. Không có hành vi suy biến.

Lỗi phổ biến nhất là quên lưu next_node trước khi ghi đè curr.next. Điều đó phá hủy tham chiếu đến phần còn lại của danh sách và không có cách nào khôi phục. Lỗi phổ biến thứ hai là trả về head thay vì prev ở cuối vòng lặp iterative — head vẫn trỏ vào node đầu tiên ban đầu, giờ là tail của danh sách đã đảo.

Mental model và khi nào nhận ra pattern

Các keyword báo hiệu là "reverse," "backward," và "flip" trong ngữ cảnh linked list. Rộng hơn: bất kỳ bài nào cần chỉnh sửa pointer .next in-place mà không cần thêm storage. Hình dạng luôn giống nhau — bạn cần nhớ đồng thời bạn đến từ đâu, đang ở đâu, và sẽ đi đâu. Đó chính xác là những gì prev, curr, và next_node theo dõi.

Mental model: chain đã đảo ngược tăng trưởng về phía trái trong khi chain gốc thu nhỏ về phía phải. Khi curr đến None, chain trái chính là danh sách đảo ngược đầy đủ.

Đây là bài đầu tiên trong series linked list. Nó xây dựng thói quen thao tác pointer cơ bản — lưu trước khi ghi đè — mà mọi bài tiếp theo đều dựa vào.

Các bài liên quan và twist mỗi bài thêm vào

• 92. Reverse Linked List II — đảo ngược sublist từ vị trí left đến right. Cùng three-pointer technique, nhưng bạn phải tìm điểm bắt đầu của subrange trước và khâu lại segment đã đảo vào xung quanh danh sách.
• 25. Reverse Nodes in k-Group — reversal áp dụng cho các cửa sổ độ dài k. Bạn gọi iterative reversal helper nhiều lần khi duyệt danh sách; phần khó là xử lý nhóm cuối khi còn ít hơn k node.
• 24. Swap Nodes in Pairs — trường hợp đặc biệt của k-group reversal với k = 2. Constraints cho phép dùng recursive tự nhiên hơn ở đây vì độ dài danh sách tối đa là 100 (không có rủi ro stack overflow).
• 143. Reorder List — tìm midpoint (Floyd's cycle detection), đảo ngược nửa sau bằng chính thuật toán này, rồi interleave hai nửa. Reversal là một trong ba bước riêng biệt.
• 234. Palindrome Linked List — đảo ngược nửa sau, so sánh từng phần tử với nửa đầu, tùy chọn khôi phục. Reversal ở đây là subroutine với yêu cầu cleanup.

Thói quen đang được xây dựng ở đây là "lưu trước khi ghi đè." Mọi bài linked list chỉnh sửa .next in-place đều dựa trên đúng thói quen đó.