Cấu trúc dữ liệu và Giải thuật Bài 30: Bài toán kinh điển: Đảo ngược danh sách liên kết (Reverse Linked List).

Nếu có một câu hỏi phỏng vấn nào định hình toàn bộ tư duy về con trỏ, thì đó chính là Reverse Linked List (Đảo ngược danh sách liên kết). Hầu hết các công ty công nghệ lớn đều dùng bài toán này làm bộ lọc đầu tiên. Đối với một kỹ sư backend thường xuyên xử lý logic phức tạp bằng Golang, hoặc khi Hiếu phác thảo các chuỗi bài viết kỹ thuật trên Viblo, việc giải thích trôi chảy thuật toán này là minh chứng rõ ràng nhất cho khả năng kiểm soát bộ nhớ không gian hẹp.

1. Nút thắt của việc đảo chiều con trỏ

Bài toán yêu cầu: Cho điểm bắt đầu (Head) của một danh sách liên kết đơn (Singly Linked List). Hãy đảo ngược chiều của tất cả các con trỏ và trả về Head mới (vốn là phần tử cuối cùng của mảng cũ).

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> nil

• Output: 5 -> 4 -> 3 -> 2 -> 1 -> nil

Nghe có vẻ đơn giản: Chỉ cần lấy Node hiện tại, trỏ ngược con trỏ Next về Node phía trước nó là xong.

Thảm họa xảy ra ở đây: Giả sử bạn đang ở Node 2. Con trỏ Next của 2 đang chỉ tới 3. Nếu bạn lập tức ép 2.Next = 1, sợi dây liên kết tới 3 bị đứt phựt. Toàn bộ phần danh sách từ 3 trở về sau trôi dạt vào vùng không gian vô định (Memory Leak) và vĩnh viễn không thể truy xuất được nữa.

2. Nghệ thuật Tung hứng 3 con trỏ (3-Pointer Technique)

Để thực hiện ca phẫu thuật này mà không làm đứt mạch máu, chúng ta cần tung hứng 3 con trỏ cùng một lúc:

1. prev (Node trước đó): Khởi tạo bằng nil. Nó sẽ đóng vai trò là bến đỗ mới cho con trỏ Next của Node hiện tại.

2. current (Node hiện tại): Bắt đầu từ Head. Đây là Node đang nằm trên bàn mổ.

3. nextTemp (Node tạm thời): Biến cứu sinh. Nó dùng để "giữ hộ" phần còn lại của danh sách trước khi chúng ta cắt đứt liên kết.

Quy trình phẫu thuật 4 bước tại mỗi Node:

• Bước 1: nextTemp = current.Next (Nắm chặt Node phía sau để không bị mất dấu).

• Bước 2: current.Next = prev (Cắt đứt liên kết cũ, trỏ ngược về Node phía trước).

• Bước 3: prev = current (Dời prev lên vị trí của current để chuẩn bị cho nhịp tiếp theo).

• Bước 4: current = nextTemp (Dời current sang Node tiếp theo đã được giữ hộ ở Bước 1).

3. Triển khai thuật toán bằng Golang

Đoạn mã sau giải quyết bài toán với độ phức tạp thời gian $O(n)$ (chỉ duyệt mảng đúng 1 lần) và độ phức tạp không gian $O(1)$ (chỉ dùng đúng 3 biến con trỏ, không cấp phát thêm Node mới).

Go

// Định nghĩa cấu trúc Node
type Node struct {
    Data int
    Next *Node
}

func reverseList(head *Node) *Node {
    var prev *Node = nil
    current := head

    for current != nil {
        // Bước 1: Giữ lại phần đuôi danh sách
        nextTemp := current.Next 
        
        // Bước 2: Đảo chiều con trỏ
        current.Next = prev      
        
        // Bước 3 & 4: Tịnh tiến cả 2 con trỏ lên 1 nhịp
        prev = current           
        current = nextTemp       
    }

    // Khi current chạy đến nil, prev chính là Node cuối cùng của danh sách cũ.
    // Nó nay trở thành Head của danh sách mới.
    return prev 
}

Mô phỏng với 1 -> 2 -> 3 -> nil:

• Khởi tạo: prev = nil, current = 1.

• Vòng 1: nextTemp = 2. Trỏ 1.Next = nil (Node 1 giờ thành đuôi). prev = 1, current = 2.

• Vòng 2: nextTemp = 3. Trỏ 2.Next = 1. prev = 2, current = 3.

• Vòng 3: nextTemp = nil. Trỏ 3.Next = 2. prev = 3, current = nil.

• Vòng lặp kết thúc. Hàm trả về prev (tức là Node 3). Chuỗi mới: 3 -> 2 -> 1 -> nil.

4. Ứng dụng thực tiễn của Đảo ngược Linked List

Bài toán này không chỉ nằm trên giấy, cấu trúc logic của nó được ứng dụng sâu trong các nghiệp vụ backend:

• Tính toán số nguyên lớn (Big Integer Arithmetic): Khi cộng hai số nguyên khổng lồ (vượt quá giới hạn uint64), hệ thống lưu trữ chúng dưới dạng danh sách liên kết. Vì phép cộng phải thực hiện từ hàng đơn vị trở lên (từ phải sang trái), ta buộc phải đảo ngược danh sách liên kết để có thể duyệt và cộng từ chỉ số thấp nhất.

• Cơ chế LIFO (Last-In-First-Out) giả lập: Nếu hệ thống chỉ hỗ trợ thao tác chèn vào đuôi (Append), việc đảo ngược toàn bộ chuỗi giúp nhanh chóng lấy ra các log hoặc giao dịch mới nhất để hiển thị cho người dùng.

• Thuật toán Undo/Redo: Trong các trình soạn thảo, việc rollback trạng thái về các bước trước đó đòi hỏi thao tác du hành ngược trên các node dữ liệu trạng thái.

Bạn đã nắm vững cách thay đổi cấu trúc của Linked List. Tuy nhiên, Linked List còn ẩn chứa một cái bẫy nguy hiểm có thể làm treo cứng toàn bộ hệ thống (Infinite Loop) nếu một con trỏ vô tình trỏ nhầm vào người tiền nhiệm của nó. Ở bài học tiếp theo, chúng ta sẽ học cách phát hiện cái bẫy này.