การพิมพ์ Immutable Linked List ย้อนหลังใน C++

สมมติว่าเรามี Immutable Linked List (Linked List ที่ไม่สามารถแก้ไขโครงสร้างได้) เราต้องพิมพ์ค่าของทุกโหนด (Node) เรียงจากหลังมาหน้า โดยใช้ Interface ที่กำหนดดังนี้:

• ImmutableListNode : Interface ของ Immutable Linked List เราจะได้รับ Head ของ List

ฟังก์ชันที่ใช้ได้มีเพียง 2 ตัว:

• ImmutableListNode.printValue() : พิมพ์ค่าของโหนดปัจจุบัน
• ImmutableListNode.getNext() : คืนค่าโหนดถัดไป

ตัวอย่าง: หาก List เป็น [0, -4, -1, 3, -5] ผลลัพธ์ที่ต้องการคือ [-5, 3, -1, -4, 0]

แนวทางแก้ปัญหา (Algorithm)

เนื่องจากไม่สามารถเดินย้อนหลังได้ (Immutable และ Singly Linked) เราจึงใช้ Stack ช่วยเก็บโหนดไว้ แล้วค่อย Pop มาพิมพ์ทีละตัว (LIFO)

1. สร้าง Stack st สำหรับเก็บ Pointer ของ ImmutableListNode
2. เดินผ่าน List ตั้งแต่ Head จนจบ (head != null):
   • Push head เข้า Stack
   • ย้าย head = head->getNext()
3. เมื่อ Stack ไม่ว่าง:
   • เรียก st.top()->printValue() เพื่อพิมพ์ค่า
   • st.pop() ลบออก

ตัวอย่างโค้ด C++

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        stack<ImmutableListNode*> st;

        // Phase 1: Push all nodes onto stack
        while (head) {
            st.push(head);
            head = head->getNext();
        }

        // Phase 2: Pop and print (Reverse order)
        while (!st.empty()) {
            st.top()->printValue();
            st.pop();
        }
    }
};

Input / Output

Input:  [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]

ความซับซ้อน (Complexity)

• Time: O(N) — เดินผ่าน List 1 รอบ + Pop Stack 1 รอบ
• Space: O(N) — เก็บ Pointer ทุกโหนดใน Stack

วิธีนี้เรียบง่าย ชัดเจน และเป็นวิธีมาตรฐานสำหรับการ Reverse Linked List แบบ Immutable ครับ