试编写链表插入排序的算法。
时间: 2023-06-15 16:06:07 浏览: 53
链表插入排序的算法可以分为以下几个步骤:
1. 如果链表为空或只有一个节点,则不需要排序,直接返回链表头节点。
2. 定义一个新的空链表,作为排序后的链表。
3. 遍历原链表,取出一个节点,将其从原链表中删除,并插入到新链表中,使新链表保持有序。
4. 重复第3步,直到原链表为空。
5. 返回新链表的头节点。
下面是链表插入排序的具体实现:
```
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insertionSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* dummy = new ListNode(0);
while (head != NULL) {
ListNode* cur = head;
head = head->next;
cur->next = NULL;
ListNode* p = dummy;
while (p->next != NULL && p->next->val < cur->val) {
p = p->next;
}
cur->next = p->next;
p->next = cur;
}
return dummy->next;
}
```
其中,`dummy`节点是一个虚拟的头节点,它的作用是使新链表的插入操作更加简单。在遍历原链表时,取出的节点是`cur`,在新链表中找到`cur`应该插入的位置时,使用指针`p`来遍历新链表,找到`cur`应该插入的位置,然后将`cur`插入到`p`后面。