แบ่ง Linked List เป็นสองส่วนตามอัตราส่วน p:q ใน C++

บทนำ

โปรแกรมนี้แบ่ง Linked List เดียวออกเป็นสอง Linked List ตามอัตราส่วน p:q โดยการตัดลิงก์ที่โหนดที่ p

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

1. สร้างโครงสร้างโหนด Linked List
2. สร้าง Linked List ตัวอย่าง
3. กำหนดอัตราส่วน p และ q
4. หาความยาวของ Linked List
5. ถ้าความยาว < p+q → แบ่งไม่ได้
6. เดินไปที่โหนดที่ p แล้วตัดลิงก์ (next = NULL)
7. โหนดถัดไปกลายเป็น head ของ List ที่สอง
8. พิมพ์ทั้งสอง List

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

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

struct Node {
    int data;
    Node *next;
    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

void printLinkedList(Node* head) {
    Node *temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

void splitLinkedList(Node *head, int p, int q) {
    int n = 0;
    Node *temp = head;
    while (temp != NULL) {
        n += 1;
        temp = temp->next;
    }
    if (p + q > n) {
        cout << "Can't divide Linked list" << endl;
    } else {
        temp = head;
        while (p > 1) {
            temp = temp->next;
            p -= 1;
        }
        Node *head_two = temp->next;
        temp->next = NULL;
        printLinkedList(head);
        printLinkedList(head_two);
    }
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = new Node(6);
    int p = 2, q = 4;
    splitLinkedList(head, p, q);
}

ผลลัพธ์

1 -> 2 -> NULL
3 -> 4 -> 5 -> 6 -> NULL

สรุป

วิธีนี้ใช้เวลา O(n) และพื้นที่ O(1) เหมาะสำหรับการแบ่ง Linked List แบบ destructive (เปลี่ยนโครงสร้างเดิม) หากต้องการเก็บต้นฉบับ ควรคัดลอกก่อน