有一个递增有序单链表L,设计一个算法向该单链表中插入一个元素为xDe的结点,si插入后该链表仍然有序 点击复制后,将打开C知道体验页
时间: 2023-05-24 07:01:18 浏览: 129
已知单链表L为按值递增有序的,编写算法将数据元素e插入到顺序表L中,使之仍有序
5星 · 资源好评率100%
可以使用以下算法向有序单链表L中插入元素x:
1. 创建一个新的结点node,将x存储在该结点中。
2. 遍历单链表L,找到插入该结点的位置p,满足p的值小于等于x,而p的后继结点的值大于等于x。
3. 将node的指针指向p的后继结点,然后将p的指针指向node。
4. 链表中的元素已经按照升序排列,插入后该链表仍然有序。
实现代码可以参考以下示例:
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insert(struct ListNode* head, int x) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = x;
node->next = NULL;
if (head == NULL) {
head = node;
return head;
}
struct ListNode *prev = NULL, *curr = head;
while (curr != NULL && curr->val < x) {
prev = curr;
curr = curr->next;
}
if (prev == NULL) {
node->next = head;
head = node;
} else {
node->next = prev->next;
prev->next = node;
}
return head;
}
注意:该示例使用了动态内存分配,需要释放内存避免内存泄漏。
阅读全文