การจัดเรียง Linked List (Sort List) ใน C++

การจัดเรียง Linked List (Sort List)

จัดเรียง Linked List ในเวลา O(n log n) และพื้นที่ O(1) (ไม่รวม stack recursion) ใช้ Merge Sort แบบ Top-down

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

ขั้นตอนการแก้ปัญหา (Merge Sort)

1. ฟังก์ชัน merge(l1, l2) รวมสอง sorted list
2. ฟังก์ชัน sortList(head):
   • ถ้า head == null || head.next == null คืนค่า head
   • หาจุดกึ่งกลางด้วย slow/fast pointers (prev ชี้ก่อน slow)
   • prev.next = null ตัด list เป็นสองครึ่ง
   • l1 = sortList(head), l2 = sortList(slow)
   • คืนค่า merge(l1, l2)

ตัวอย่างโค้ด 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* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *slow = head, *fast = head, *prev = NULL;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = NULL;
        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(slow);
        return mergeList(l1, l2);
    }
    ListNode* mergeList(ListNode* l1, ListNode* l2) {
        ListNode dummy(0), *p = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) { p->next = l1; l1 = l1->next; }
            else { p->next = l2; l2 = l2->next; }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

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

Input: [4,2,1,3,5,9,8,6,7]

Output: [1,2,3,4,5,6,7,8,9]