Danh sách liên kết ngược C++

Trong Khoa học Máy tính, danh sách liên kết là một cấu trúc dữ liệu tuyến tính trong đó một con trỏ trong mỗi phần tử xác định thứ tự. Trong hướng dẫn này, chúng tôi sẽ chỉ cho bạn cách đảo ngược danh sách được liên kết

2. Đảo ngược danh sách liên kết

Mỗi phần tử của danh sách liên kết chứa trường dữ liệu để lưu trữ dữ liệu danh sách và trường con trỏ để trỏ đến phần tử tiếp theo trong chuỗi. Chúng ta có thể sử dụng con trỏ

để trỏ đến phần tử bắt đầu của danh sách liên kết.

Sau khi đảo ngược danh sách liên kết thì sẽ trỏ đến phần tử cuối cùng của danh sách liên kết ban đầu và con trỏ của mỗi phần tử sẽ trỏ đến phần tử trước đó của danh sách liên kết ban đầu .

3. Giải pháp lặp đi lặp lại

Đầu tiên, hãy giải quyết một phiên bản đơn giản hơn của vấn đề. đảo ngược danh sách liên kết có hai phần tử

Giả sử con trỏ

trỏ đến phần tử thứ hai và con trỏ trỏ đến phần tử trước phần tử .

=
=

Đối với danh sách được liên kết có nhiều hơn hai phần tử, chúng ta có thể duyệt qua danh sách được liên kết và sử dụng cùng một chiến lược để đảo ngược con trỏ tiếp theo của phần tử hiện tại

Trong thuật toán lặp này, trước tiên chúng ta đặt con trỏ là con trỏ và là < . Sau đó, trong mỗi lần lặp của vòng lặp, chúng ta đảo ngược con trỏ được liên kết của hai phần tử này và chuyển con trỏ . Then, in each iteration of the loop, we reverse the linked pointer of these two elements and shift the và sang hai phần tử tiếp theo. Cuối cùng, con trỏ sẽ trỏ đến phần tử đầu mới của danh sách liên kết ngược.

Vì mỗi phần tử chỉ có một tham chiếu đến phần tử tiếp theo nên chúng ta cần một con trỏ khác,

, để lưu phần tử tiếp theo trước khi thay đổi con trỏ .

Vòng lặp duyệt qua toàn bộ danh sách liên kết một lần. Do đó, thời gian chạy của thuật toán lặp là

, trong đó là tổng số phần tử của danh sách liên kết.

4. Giải pháp đệ quy

Chúng ta cũng có thể giải bài toán bằng giải pháp đệ quy. Trước tiên hãy xem xét một trường hợp đơn giản hơn khi chúng ta đảo ngược phần còn lại của danh sách liên kết sau phần tử .

Ta chỉ cần đảo ngược hai phần tử. và

. Lúc đầu, con trỏ của là . Chúng ta nên thay đổi điều đó để làm cho nó trỏ tới . Sau đó ta đổi con trỏ next của phần tử thành để kết thúc việc đảo ngược.

=
=

Chúng ta có thể mở rộng giải pháp này thành thuật toán đệ quy để đảo ngược danh sách được liên kết bắt đầu bằng phần tử . Đầu tiên, chúng ta có thể đảo ngược danh sách được liên kết bắt đầu bằng phần tử bằng cách gọi đệ quy hàm đảo ngược của chúng ta. Sau đó, danh sách được liên kết trở thành trường hợp đơn giản hơn của chúng tôi. Do đó, chúng ta có thể đảo ngược hai phần tử cuối cùng là và bằng hai thao tác trên.

Chúng ta có thể xây dựng một thuật toán đệ quy dựa trên cách tiếp cận này

Trong thuật toán đệ quy này, trước tiên chúng tôi kiểm tra các trường hợp cơ sở trong đó con trỏ đầu vào là hoặc trỏ đến một phần tử đơn lẻ. Sau đó, chúng ta gọi đệ quy hàm

trên phần tử để đảo ngược phần còn lại của danh sách liên kết. Cuối cùng, chúng ta đảo ngược các phần tử và để kết thúc việc đảo ngược.

Thuật toán đệ quy cũng duyệt qua toàn bộ danh sách liên kết một lần. Do đó, thời gian chạy là , trong đó là tổng số phần tử của danh sách liên kết.

5. Phần kết luận

Trong hướng dẫn này, chúng tôi đã trình bày một danh sách liên kết mẫu và sự đảo ngược của nó. Ngoài ra, chúng tôi đã thảo luận về hai thuật toán có thể đảo ngược danh sách được liên kết trong thời gian tuyến tính

tác giả dưới cùng

Nếu bạn có một vài năm kinh nghiệm trong Khoa học máy tính hoặc nghiên cứu và bạn muốn chia sẻ kinh nghiệm đó với cộng đồng, hãy xem Nguyên tắc đóng góp của chúng tôi