Partition List - แบ่ง Linked List ตามค่า x ใน C++

ภาพรวมปัญหา

มี Linked List และค่า x ต้องจัดเรียงใหม่ให้โหนดที่น้อยกว่า x อยู่หน้า โหนดที่มากกว่าหรือเท่า x อยู่หลัง รักษาลำดับเดิมในแต่ละกลุ่ม

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

อัลกอริทึม (Two Dummy Lists)

1. สร้าง dummy1, dummy2 (ค่า -1), dp1, dp2 ชี้ไปที่ dummy1, dummy2
2. while a ไม่ใช่ null:
   • ถ้า a->val < x: dp1->next = new ListNode(a->val), dp1 = dp1->next
   • else: dp2->next = new ListNode(a->val), dp2 = dp2->next
   • a = a->next
3. dp1->next = dummy2->next
4. return dummy1->next

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

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

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

ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i < v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr->next){ cout << ptr->val << ", "; ptr = ptr->next; }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* partition(ListNode* a, int b) {
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        ListNode* dummyPtr1 = dummy1;
        ListNode* dummyPtr2 = dummy2;
        while(a){
            if(a->val < b){
                dummyPtr1->next = new ListNode(a->val);
                dummyPtr1 = dummyPtr1->next;
            } else {
                dummyPtr2->next = new ListNode(a->val);
                dummyPtr2 = dummyPtr2->next;
            }
            a = a->next;
        }
        dummyPtr1->next = dummy2->next;
        return dummy1->next;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,4,6,3,2,5,2,8};
    ListNode *head = make_list(v);
    print_list(ob.partition(head, 3));
}

Input / Output

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