วิธีการเรียกซ้ำสำหรับแบ่ง Linked List สลับกันใน C++

ภาพรวม

เมื่อได้รับ Singly Linked List เป็นอินพุต เป้าหมายคือแบ่งลิสต์ออกเป็นสอง Singly Linked List ที่มีโหนดสลับกันจากลิสต์เดิม ตัวอย่าง: ลิสต์ a → b → c → d → e → f จะแบ่งเป็น a → c → e และ b → d → f

ใช้สองพอยน์เตอร์ N1 และ N1 ชี้ที่หัวและหัว→next ตามลำดับ จากนั้นเลื่อนทั้งคู่ไปที่ next ของ next เพื่อสร้างสับลิสต์

ตัวอย่าง

อินพุต − ลิสต์: 1 → 5 → 7 → 12 → 2 → 96 → 33

เอาต์พุต − ลิสต์เดิม: 1 5 7 12 2 96 33

ลิสต์ 1: 1 7 2 33

ลิสต์ 2: 5 12 96

คำอธิบาย − เริ่มจาก 1 และ 5 แล้วชี้ไปที่โหนดสลับกันเพื่อสร้างสับลิสต์

อินพุต − ลิสต์: 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32

เอาต์พุต − ลิสต์เดิม: 13 53 90 18 44 11 99 32

ลิสต์ 1: 13 90 44 99

ลิสต์ 2: 53 18 11 32

คำอธิบาย − เริ่มจาก 13 และ 53 แล้วชี้ไปที่โหนดสลับกัน

แนวทางการแก้ปัญหา

ใช้สองพอยน์เตอร์ N1 และ N2 ชี้ที่หัวและหัว→next ตามลำดับ เลื่อนทั้งคู่ไปที่ next ของ next แบบเรียกซ้ำเพื่อสร้างสองสับลิสต์

• โครงสร้าง Node มี int data และ Node* next
• ฟังก์ชัน addtohead(Node** head, int data) เพิ่มโหนดที่หัว
• สร้าง Singly Linked List
• ฟังก์ชัน display(Node* head) พิมพ์ลิสต์
• สองพอยน์เตอร์ node1 และ node2
• ฟังก์ชัน splitList(Node* head, Node** n1, Node** n2) ตั้ง n1 ชี้หัว และ n2 ชี้หัว→next แล้วเรียก split
• ฟังก์ชัน split(Node* N1, Node* N2) สร้างสับลิสต์สลับกัน
• ถ้า N1 และ N2 เป็น NULL คืนค่า
• ถ้า N1→next ไม่เป็น NULL ตั้ง tmp = N1->next->next และ N1->next = tmp
• ถ้า N2→next ไม่เป็น NULL ตั้ง tmp = N2->next->next และ N2->next = tmp
• เรียก split(N1->next, N2->next) ต่อ
• พิมพ์สับลิสต์ด้วย display()

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

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

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

void addtohead(Node** head, int data){ 
    Node* nodex = new Node; 
    nodex->data = data; 
    nodex->next = (*head); 
    (*head) = nodex; 
} 

void split(Node* N1, Node* N2){ 
    Node *tmp; 
    if (N1 == NULL || N2 == NULL){ 
        return; 
    } 
    if (N1->next != NULL){ 
        tmp = N1->next->next; 
        N1->next = tmp; 
    } 
    if (N2->next != NULL){ 
        tmp = N2->next->next; 
        N2->next = tmp; 
    } 
    split(N1->next, N2->next); 
} 

void splitList(Node* head, Node** n1, Node** n2){ 
    *n1 = head; 
    *n2 = head->next; 
    split(*n1, *n2); 
} 

void display(Node* head){ 
    Node* curr = head; 
    if (curr != NULL){ 
        cout << curr->data << " "; 
        display(curr->next); 
    } 
} 

int main(){ 
    Node* head = NULL; 
    Node *node1 = NULL, *node2 = NULL; 
    addtohead(&head, 20); 
    addtohead(&head, 12); 
    addtohead(&head, 15); 
    addtohead(&head, 8); 
    addtohead(&head, 10); 
    addtohead(&head, 4); 
    addtohead(&head, 5); 
    cout << "Original List :" << endl; 
    display(head); 
    splitList(head, &node1, &node2); 
    cout << endl << "List 1: "; 
    display(node1); 
    cout << endl << "List 2: "; 
    display(node2); 
    return 0; 
}

ผลลัพธ์

Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12