Giới thiệu
Trong loạt bài viết về thuật toán chuyên sâu, chúng ta hôm nay sẽ tìm hiểu về một thuật toán rất phổ biến: đảo ngược chuỗi liên kết đơn (Linked List). Trong bài viết này, chúng ta sẽ sử dụng ngôn ngữ Java để triển khai thuật toán.
Đảo ngược chuỗi liên kết (LinkedList)
Linked List là một cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu theo cách tuyến tính. Mỗi phần tử của Linked List bao gồm một dữ liệu và địa chỉ của phần tử tiếp theo trong Linked List. Các phần tử trong Linked List thường được gọi là các node.
Để đảo ngược một Linked List, quan trọng là chúng ta cần đảo ngược các con trỏ sao cho phần tử tiếp theo trỏ đến phần tử trước đó.
Dưới đây là minh họa cho input và output:
Đầu vào: 
Kết quả sau khi chạy thuật toán: 
Phần head của Linked List là node đầu tiên. Không có phần tử nào có địa chỉ được lưu trữ ở vị trí này. Phần đuôi của Linked List là node cuối cùng. Địa chỉ tiếp theo được lưu trữ ở node này là null.
Có hai phương pháp để đảo ngược một danh sách liên kết đơn (Linked List):
1. Sử dụng vòng lặp
Để đảo ngược một Linked List theo cách Iterative, chúng ta cần lưu trữ các tham chiếu của phần tử next và phần tử previous để không mất đi khi ta hoán đổi con trỏ địa chỉ bộ nhớ sang phần tử next trong Linked List.
Dưới đây là minh họa cách ta đảo ngược Linked List bằng cách thay đổi các tham chiếu:
2. Sử dụng phương pháp đệ quy (recursive)
Để đảo ngược một Linked List theo phương pháp đệ quy, ta cần chia Linked List thành hai phần: phần head và phần còn lại. Ban đầu, phần head chỉ đến phần tử đầu tiên. Phần còn lại chỉ đến phần tử tiếp theo từ phần head.
Ta duyệt lần lượt các phần tử của danh sách bằng cách sử dụng đệ quy cho đến phần tử cuối cùng thứ hai. Khi ta đã đến phần tử cuối cùng, ta đặt phần tử đó làm phần head. Từ đó, ta thực hiện các bước sau cho đến khi bắt đầu vào Linked List.
Để không mất dấu vết của head gốc, ta sẽ lưu một bản sao của head instance.
Dưới đây là minh họa cách ta đảo ngược Linked List bằng cách sử dụng đệ quy:
Kết luận
Cả hai phương pháp đảo ngược Linked List đều có hiệu quả và có thể được áp dụng tùy thuộc vào yêu cầu cụ thể của dự án. Chúng ta đã tìm hiểu cách triển khai thuật toán này bằng ngôn ngữ Java và cũng đã xem qua ví dụ chi tiết.
Cảm ơn bạn đã dành thời gian theo dõi bài viết này. Hãy like và comment nếu bạn thấy hữu ích! ❤
Bài viết gốc được đăng tải tại vntalking.com
Xem thêm:
- Ứng dụng thuật toán và cấu trúc dữ liệu lúc đi làm
- Phân biệt ArrayList và LinkedList
- Sử dụng thuật toán quay lui giải bài toán phân tích số bằng JavaScript
