将一个非递增有序的线性表变成递增有序的线性表,如果线性表中有数值相同的元素存在,去掉数值相同的元素,使表中不再有重复的元素。例如:(70,66,66,57,48,30,30,11,9)将变作(9,11,30,48,57,66,70)。若存储方式为单链表,试设计算法实现这一过程。
时间: 2023-04-29 20:03:02 浏览: 104
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
算法步骤如下:
1. 定义两个指针p和q,p指向链表的头结点,q指向p的下一个节点。
2. 遍历链表,如果p节点的值等于q节点的值,则删除q节点,并将p节点的next指针指向q节点的next节点,否则p指针和q指针同时后移一位。
3. 遍历完链表后,链表中的重复元素已经被删除,接下来进行排序。定义一个新的指针r,指向链表的头结点。
4. 遍历链表,每次找到最小的节点,并将其与r节点交换值,然后r节点后移一位。
5. 遍历完链表后,链表已经变成了递增有序的链表。
算法实现如下:
```
void sortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != NULL) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = p->next;
q = q->next;
}
}
ListNode* r = head;
while (r != NULL) {
ListNode* minNode = r;
ListNode* curNode = r->next;
while (curNode != NULL) {
if (curNode->val < minNode->val) {
minNode = curNode;
}
curNode = curNode->next;
}
swap(r->val, minNode->val);
r = r->next;
}
}
```
阅读全文