C++ การแบ่ง Linked List รอบค่าที่กำหนดพร้อมรักษาลำดับเดิม

ในบทช่วยสอนนี้ ให้ Linked List มา เราต้องเก็บตัวเลขที่น้อยกว่า x ไว้หน้ารายการ และตัวอื่นๆ ไว้ท้ายรายการ เรายังต้องรักษาลำดับเดิมเหมือนเดิม เช่น

Input : 1->4->3->2->5->2->3, x = 3 Output: 1->2->2->3->3->4->5
Input : 1->4->2->10 x = 3 Output: 1->2->4->10
Input : 10->4->20->10->3 x = 3 Output: 3->10->4->20->10

เพื่อแก้ปัญหานี้ เราต้องสร้าง Linked List สามตัว ตอนที่เราพบตัวเลขน้อยกว่า x เราแทรกลงรายการแรก สำหรับค่าเท่ากับ x ใส่รายการที่สอง สำหรับค่ามากกว่า ใส่รายการที่สาม ตอนท้ายเราเชื่อมต่อรายการทั้งสามและพิมพ์รายการสุดท้าย

วิธีการแก้ปัญหา

ในวิธีนี้ เราจะดูแลรักษาสามรายการ คือ small, equal, large เรารักษาลำดับของพวกเขาและเชื่อมต่อรายการเข้าด้วยกันเป็นรายการสุดท้ายซึ่งเป็นคำตอบของเรา

ตัวอย่าง

โค้ด C++ สำหรับวิธีการข้างต้น

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

struct Node{ 
    int data; 
    struct Node* next; 
}; 

Node *newNode(int data){ 
    struct Node* new_node = new Node; 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
} 

struct Node *partition(struct Node *head, int x){ 
    struct Node *smallhead = NULL, *smalllast = NULL; 
    struct Node *largelast = NULL, *largehead = NULL; 
    struct Node *equalhead = NULL, *equallast = NULL; 
    while (head != NULL){ 
        if (head->data == x){ 
            if (equalhead == NULL) equalhead = equallast = head; 
            else{ equallast->next = head; equallast = equallast->next; } 
        } else if (head->data < x){ 
            if (smallhead == NULL) smalllast = smallhead = head; 
            else{ smalllast->next = head; smalllast = head; } 
        } else{ 
            if (largehead == NULL) largelast = largehead = head; 
            else{ largelast->next = head; largelast = head; } 
        } 
        head = head->next; 
    } 
    if (largelast != NULL) largelast->next = NULL; 
    if (smallhead == NULL){ 
        if (equalhead == NULL) return largehead; 
        equallast->next = largehead; return equalhead; 
    } 
    if (equalhead == NULL){ 
        smalllast->next = largehead; return smallhead; 
    } 
    smalllast->next = equalhead; 
    equallast->next = largehead; 
    return smallhead; 
} 

void printList(struct Node *head){ 
    struct Node *temp = head; 
    while (temp != NULL){ 
        printf("%d ", temp->data); 
        temp = temp->next; 
    } 
} 

int main(){ 
    struct Node* head = newNode(10); 
    head->next = newNode(4); 
    head->next->next = newNode(5); 
    head->next->next->next = newNode(30); 
    head->next->next->next->next = newNode(2); 
    head->next->next->next->next->next = newNode(50); 
    int x = 3; 
    head = partition(head, x); 
    printList(head); 
    return 0; 
}

ผลลัพธ์

2 10 4 5 30

คำอธิบายโค้ด

ในวิธีที่อธิบายข้างต้น เราจะเก็บ Linked List สามรายการที่มีเนื้อหาเรียงลำดับ สามรายการนี้จะมีสมาชิกที่น้อยกว่า เท่ากับ และมากกว่า x แยกกัน ภารกิจของเราก็ง่ายขึ้น เราต้องแค่เชื่อมต่อรายการแล้วคืนค่า Head

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Partitioning a linked list around a given value and keeping the original order เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์