รวมสองรายการที่เชื่อมโยงที่เรียงลำดับโดยใช้ C ++

คำชี้แจงปัญหา

ให้ 2 เรียงลำดับรายการเชื่อมโยงเดี่ยว เขียนฟังก์ชันเพื่อรวมรายการเชื่อมโยงที่เรียงลำดับสองรายการ

List1:10->15->17->20List2:5->9->13->19ผลลัพธ์:5->9->10->13->15->17->19->20

อัลกอริทึม

<ก่อน>1. สำรวจทั้งสองรายการ 1.1 ถ้า list1->data data 1.1.1 เพิ่ม list1->data ไปยังรายการใหม่และเพิ่ม list1 ตัวชี้ 1.2 ถ้า list2->data data 1.2.1 เพิ่ม list2->data ไปยังรายการใหม่และเพิ่ม list2 ตัวชี้2. ทำซ้ำขั้นตอนจนกว่าทั้งสองรายการจะหมดแล้ว3. กลับรายการผลลัพธ์

ตัวอย่าง

#include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;struct node { ข้อมูล int; struct node *next;};node *createList(int *arr, int n){ โหนด *หัว, *p; p =หัว =โหนดใหม่; head->data =arr[0]; head->next =NULL; สำหรับ (int i =1; i next =โหนดใหม่; p =p->ถัดไป; p->data =arr[i]; p->ถัดไป =NULL; }return head;}void displayList(node *head){ while (head !=NULL) { cout <data <<" "; หัว =หัว -> ถัดไป; } cout <data data) { ผลลัพธ์ =head1; ผลลัพธ์ -> ถัดไป =mergeSortedLists (head1-> ถัดไป, head2); } อื่น ๆ { ผล =head2; ผลลัพธ์ -> ถัดไป =mergeSortedLists (head1, head2->next); } ส่งคืนผลลัพธ์;}int main(){ int arr1[] ={10, 15, 17, 20}; int arr2[] ={5, 9, 13, 19}; โหนด *head1, *head2, *ผลลัพธ์ =NULL; head1 =createList(arr1, SIZE(arr1)); head2 =createList(arr2, SIZE(arr1)); cout <<"เรียงลำดับรายการแรก:" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 เรียงลำดับรายการแรก:10 15 17 20เรียงลำดับรายการที่สอง:5 9 13 19เรียงลำดับรายการสุดท้าย:5 9 10 13 15 17 19 20