在C++中,要對鏈表進行排序,可以使用自定義比較函數作為qsort的參數。以下是一個使用qsort對鏈表進行排序的示例:
首先,定義一個鏈表節點結構體:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
然后,實現一個自定義比較函數,用于比較兩個鏈表節點的值:
bool compare(ListNode *a, ListNode *b) {
return a->val < b->val;
}
接下來,編寫一個函數,用于將鏈表轉換為數組,以便使用qsort進行排序:
int* linkedListToArray(ListNode *head, int &size) {
size = 0;
ListNode *current = head;
while (current != NULL) {
size++;
current = current->next;
}
int *arr = new int[size];
current = head;
for (int i = 0; i < size; i++) {
arr[i] = current->val;
current = current->next;
}
return arr;
}
最后,編寫一個函數,用于釋放鏈表占用的內存:
void freeList(ListNode *head) {
ListNode *current = head;
while (current != NULL) {
ListNode *next = current->next;
delete current;
current = next;
}
}
現在,你可以使用qsort對鏈表進行排序了:
int main() {
// 創建一個鏈表:1 -> 3 -> 2 -> 5 -> 4
ListNode *head = new ListNode(1);
head->next = new ListNode(3);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(5);
head->next->next->next->next = new ListNode(4);
int size;
int *arr = linkedListToArray(head, size);
// 使用qsort對數組進行排序
qsort(arr, size, sizeof(int), compare);
// 將排序后的數組轉換回鏈表
head = NULL;
for (int i = 0; i < size; i++) {
ListNode *newNode = new ListNode(arr[i]);
newNode->next = head;
head = newNode;
}
// 打印排序后的鏈表:1 -> 2 -> 3 -> 4 -> 5
ListNode *current = head;
while (current != NULL) {
cout << current->val << " -> ";
current = current->next;
}
cout << "NULL" << endl;
// 釋放鏈表占用的內存
freeList(head);
return 0;
}
這個示例中,我們首先創建了一個鏈表,然后將其轉換為數組并使用qsort進行排序。最后,我們將排序后的數組轉換回鏈表并打印結果。