In Danh Sách Liên Kết Bất Biến Theo Thứ Tự Ngược Trong C++

Giả sử chúng ta có một danh sách liên kết bất biến (immutable linked list), chúng ta phải in ra tất cả các giá trị của từng nút theo thứ tự ngược với sự trợ giúp của giao diện sau:

• ImmutableListNode – Đây là giao diện của một danh sách liên kết bất biến, chúng ta được cho nút đầu (head) của danh sách.

Chúng ta phải sử dụng các hàm sau để truy cập danh sách liên kết:

• ImmutableListNode.printValue() – In giá trị của nút hiện tại.

• ImmutableListNode.getNext() – Trả về nút tiếp theo.

Ví dụ, nếu danh sách là: [0, -4, -1, 3, -5], thì đầu ra sẽ là [-5, 3, -1, -4, 0].

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• Định nghĩa một stack st chứa các nút kiểu ImmutableListNode.

• Khi head không phải null:

  • Đẩy head vào stack.

  • Cập nhật head := nút tiếp theo của head.

• Khi stack không rỗng:

  • In giá trị của nút ở đỉnh stack.

  • Loại bỏ nút khỏi stack.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        stack <ImmutableListNode*> st;
        while(head){
            st.push(head);
            head = head->getNext();
        }
        while(!st.empty()){
            st.top()->printValue();
            st.pop();
        }
    }
};

Đầu vào

[0,-4,-1,3,-5]

Đầu ra

[-5,3,-1,-4,0]