การจัดเรียงใหม่ Linked List (Reorder List) ใน C++

การจัดเรียงใหม่ Linked List (Reorder List)

ให้ linked list L1→L2→L3→...→Ln จัดเรียงใหม่เป็น L1→Ln→L2→L(n-1)→... โดยไม่เปลี่ยนค่าโหนด แค่เปลี่ยน pointer

ตัวอย่าง: [1,2,3,4,5] → [1,5,2,4,3]

ขั้นตอนการแก้ปัญหา

1. หาจุดกึ่งกลางด้วย slow/fast pointers
2. กลับ (reverse) ครึ่งหลังของ list
3. ผสาน (merge) สองครึ่งสลับกัน: ตัวจากครึ่งแรก, ตัวจากครึ่งหลังที่กลับแล้ว, ซ้ำไปเรื่อยๆ

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

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) { val = data; next = NULL; }
};

class Solution {
public:
    ListNode* reverse(ListNode* head, ListNode* prev = NULL) {
        if (!head) return prev;
        ListNode* temp = head->next;
        head->next = prev;
        return reverse(temp, head);
    }
    void reorderList(ListNode* head) {
        if (!head) return;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverse(slow->next);
        slow->next = NULL;
        slow = head;
        while (fast) {
            ListNode *t1 = slow->next, *t2 = fast->next;
            slow->next = fast;
            fast->next = t1;
            slow = t1;
            fast = t2;
        }
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,2,3,4,5]

Output: [1,5,2,4,3]