2.3.7, 6
- 把链表数据取出来放到数组里排序，然后再将排好序的数放回链表
- 典型的空间换时间，排序时间复杂度O(nlog2n)，空间复杂度O(n)
void sortList(LinkList &L, int len) { // 1.将链表数据复制到数组中 LNode *head = L->next; int a[len], i = 0; while (head != NULL) { a[i++] = head->data; head = head->next; } // 2.排序 sort(a, a+len); // 3.将排序后的数组复制回链表 head = L->next, i = 0; while (head != NULL) { head->data = a[i++]; head = head->next; } } 复制代码
- 插入排序，首先构造一个只有一个结点的有序列表pre
- 剩下的p链表中的元素分别找位置插入即可
- 时间复杂度O(n2)，空间复杂度O(1)
void sortList2(LinkList &L) { LNode *p = L->next, *pre; LNode *q = p->next; p->next = NULL; // 1.构建只有一个结点的有序链表 p = q; // 2.分别查找位置插入 while (p != NULL) { q = p->next; pre = L; // 找到有序的位置 while (pre->next != NULL && pre->next->data < p->data) { pre = pre->next; } // 插入 p->next = pre->next; pre->next = p; p = q; } } 复制代码
2.3.7, 7
- 这题非常的简单，直接遍历逐个检查，不符合就删除
- 双指针，删除必须有其前驱指针
- 时间复杂度O(n)，空间复杂度O(1)
void delRange(LinkList &L, int min, int max) { LNode *p = L->next, *pre = L; while (p != NULL) { if (p->data > min && p->data < max) { // 在范围内就删除 pre->next = p->next; free(p); p = pre->next; } else { // 不在范围内就继续遍历 pre = pre->next; p = p->next; } } }
