โจทย์
ลิงก์ลิสต์ เก็บค่าไว้ในโหนดที่ชี้ไปยังโหนดถัดไป การเพิ่มหรือลบที่หัวจึงทำได้ถูก จงจำลองลิสต์ที่เริ่มต้นว่างเปล่า
ประมวลผลคำสั่งตามลำดับ:
push_front x: เพิ่ม x ที่หัวpush_back x: เพิ่ม x ที่ท้ายpop_front: ลบค่าแรก (ไม่ทำอะไรถ้าลิสต์ว่าง)remove x: ลบโหนดแรกที่มีค่า x ถ้ามีreverse: กลับลำดับของโหนด
จงเขียน linked_list_operations(operations)
อินพุต
operations: คำสั่งต่าง ๆ
เอาต์พุต
คืนค่าในลิสต์จากหัวไปท้าย
เงื่อนไข
0 ≤ จำนวนคำสั่ง ≤ 10,000
−10^9 ≤ x ≤ 10^9
ตัวอย่าง
อินพุต:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
ผลลัพธ์ที่คาดหวัง:
expected = [3, 2, 1]
อินพุต:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 2, 1};
อินพุต:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 2, 1};
คำอธิบาย
ลิสต์กลายเป็น 1 → 2 → 3 และเมื่อกลับลำดับได้ [3, 2, 1]
อินพุต:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
ผลลัพธ์ที่คาดหวัง:
expected = [5]
อินพุต:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {5};
อินพุต:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {5};
คำอธิบาย
remove ลบเฉพาะ 5 ตัวแรก เหลือ 7 → 5 แล้ว pop_front ลบ 7: [5]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ชนิดลิสต์ที่เพิ่มหัวท้ายได้เร็ว (std::list, LinkedList<T>, deque) ทำงานส่วนใหญ่ให้
คำใบ้ 2
remove ลบเฉพาะตัวแรกที่ตรง และ pop_front บนลิสต์ว่างไม่ทำอะไร
คำใบ้ 3
การกลับลำดับทำให้ปลายอีกด้านกลายเป็นหัวสำหรับ push และ pop ครั้งต่อไป
ความซับซ้อนที่คาดหวัง
เวลา O(n²), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน