Danh sách liên kết — Linked List
Danh sách liên kết (linked list) là chuỗi các node, mỗi node giữ dữ liệu và một con trỏ tới node kế tiếp. Khác với mảng, nó không cho truy cập theo chỉ số trong O(1), nhưng thêm hoặc xoá tại một vị trí đã biết chỉ tốn O(1) vì chỉ phải nối lại vài con trỏ.
Các bài kinh điển xoay quanh thao tác con trỏ: đảo chiều, gộp, tìm điểm giữa, hay phát hiện chu trình bằng hai con trỏ nhanh và chậm. Lỗi hay gặp là làm đứt chuỗi vì quên lưu con trỏ next trước khi đổi liên kết.
Như đoàn tàu các toa nối nhau — mỗi toa (node) giữ hàng hoá (val) và móc nối tới toa kế (next).
- Muốn tới toa cuối phải đi qua từng toa, không nhảy thẳng theo chỉ số như mảng.
- Đổi lại, gắn/tháo một toa ở giữa chỉ là đổi vài cái móc, O(1).
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Danh sách liên kết
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| cho sẵn head | Thao tác con trỏ next thay vì chỉ số mảng |
| đảo chiều / nối / tách | Lưu next trước khi gán lại để khỏi mất chuỗi |
| nhanh & chậm | Tìm điểm giữa hoặc phát hiện chu trình |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Thêm/xoá đầu danh sách nhiều, không cần truy cập theo chỉ số
Đảo chiều, gộp, hoặc tách chuỗi node
Phát hiện chu trình bằng 2 con trỏ nhanh/chậm (fast & slow)
Dữ liệu kích thước không biết trước, không muốn copy khi mở rộng như mảng
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Cần random access theo index: Linked List O(n) mỗi truy cập — Array tốt hơn nhiều
Cần Binary Search trên dữ liệu: Linked List không random access nên không hợp
Cache-locality quan trọng cho performance: Array có lợi thế rõ rệt về CPU cache
Hình minh hoạ
Sơ đồ thể hiện cách giải của chủ đề này.
Mỗi node giữ giá trị + con trỏ tới node kế. Không truy cập ngẫu nhiên — muốn tới phần tử thứ k phải đi tuần tự từ head.
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function listPattern(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0) // node giả: gỡ rối trường hợp đầu
dummy.next = head
let prev: ListNode | null = dummy
let curr = head
while (curr) {
const nextNode = curr.next // lưu next TRƯỚC khi đổi liên kết
// ... đổi con trỏ: curr.next = ..., prev.next = ...
prev = curr
curr = nextNode
}
return dummy.next
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Truy cập node thứ i mất O(n); thêm/xoá khi đã có con trỏ tới chỗ đó là O(1)
Dùng node giả (dummy head) để xử lý gọn trường hợp đầu danh sách
Kỹ thuật 2 con trỏ: fast đi 2 bước, slow đi 1 bước — tìm điểm giữa / phát hiện chu trình
Lỗi thường gặp
Mất tham chiếu tới phần còn lại khi đảo chiều — phải lưu next trước khi gán lại
Quên trường hợp danh sách rỗng (head = null) hoặc chỉ 1 node
Truy cập node.next khi node đã là null → lỗi runtime
Độ phức tạp
Duyệt O(n), thêm/xoá tại con trỏ O(1), bộ nhớ phụ O(1)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay