โจทย์ทั้งหมด
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การดำเนินการกับลิงก์ลิสต์

จำลองลิงก์ลิสต์: เพิ่มที่ปลายทั้งสองด้าน ลบจากหัวหรือตามค่า และกลับลำดับ

สิ่งที่คุณจะได้เรียนรู้

  • เพิ่มและลบโหนดที่ปลายทั้งสองด้าน
  • ลบโหนดแรกที่มีค่าที่กำหนด
  • กลับลำดับของลิสต์

โจทย์

ลิงก์ลิสต์ เก็บค่าไว้ในโหนดที่ชี้ไปยังโหนดถัดไป การเพิ่มหรือลบที่หัวจึงทำได้ถูก จงจำลองลิสต์ที่เริ่มต้นว่างเปล่า

ประมวลผลคำสั่งตามลำดับ:

  • 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก