In danh sách liên kết bất biến trong đảo ngược trong C ++

Giả sử chúng ta có một danh sách liên kết bất biến, chúng ta phải in ngược lại tất cả các giá trị của mỗi nút với sự trợ giúp của giao diện sau -

• ImmutableListNode - Đây là một giao diện của một danh sách liên kết bất biến, chúng tôi được đặt ở đầu danh sách.

Chúng tôi phải sử dụng các chức năng sau để truy cập danh sách liên kết -

• ImmutableListNode.printValue () - Điều này sẽ in ra giá trị của nút hiện tại.

• ImmutableListNode.getNext () −Điều này sẽ trả về nút tiếp theo.

Vì vậy, nếu danh sách như sau:[0, -4, -1, 3, -5], thì đầu ra sẽ là [-5, 3, -1, -4, 0]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một ngăn xếp cho nút loại ImmutableListNode

• trong khi phần đầu không rỗng

  • chèn đầu vào st

  • head:=next of head

• trong khi st không trống

  • in giá trị của nút trên cùng của ngăn xếp

  • xóa nút khỏi ngăn xếp

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách 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]