19
- 遍历循环单链表，每循环一次查找一个最小结点（循环单链表，注意循环终止条件！）
- minp指向最小值结点，minpre指向其前驱
- 输出其值然后删除，循环结束后释放头结点
- 时间复杂度O(n2)，空间复杂度O(1)
void delMin(LinkList L) { // 1.创建工作指针，遍历 LNode *p, *pre, *minp, *minpre; while (L->next != L) { pre = L, p = L->next; minpre = pre, minp = p; // 2.找到最小值，记录其前缀 while (p != L) { if (p->data < minp->data) { minp = p; minpre = pre; } pre = p; p = p->next; } // 3.输出并释放最小值结点 cout << minp->data << ' '; minpre->next = minp->next; free(minp); } // 4.释放头结点 free(L); } 复制代码
- 每次删除最小值结点，我们只需要记录最小值前缀即可
- 每次都用
minpre->next进行比较 - 时间复杂度O(n2)，空间复杂度O(1)
void delMin2(LinkList L) { // 1.只剩一个头结点时停止 while (L->next != L) { LNode *minpre = L, *p = L->next; // 2.找到最小值，记录其前缀 while (p->next != L) { if (p->next->data < minpre->next->data) minpre = p; p = p->next; } // 3.输出并释放最小值结点 cout << minpre->next->data << ' '; LNode *del = minpre->next; minpre->next = del->next; free(del); } // 4.释放头结点 free(L); } 复制代码
- 如果只考虑输出的话，有一个取巧的方法
- 我们把链表的值取出来放在一个数组中排序输出
- 最后释放链表空间即可
- 用了cpp的
sort()，所以时间复杂度O(nlog2n)，空间复杂度O(n)
int getLength(LinkList L) { int i = 0; LNode *p = L->next; while (p != L) { p = p->next; i++; } return i; } void delMin3(LinkList L) { int len = getLength(L); int a[len], i = 0; LNode *head = L->next; while (head != L) { a[i++] = head->data; head = head->next; } sort(a, a+len); for (int i = 0; i < len; i++) cout << a[i] << ' '; puts(""); // 释放所有结点空间，此处省略 }
