19,设有一个带头结点的循环单链表,其结点值均为正整数。设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头结点。
思路：设置双指针，p,q；p用来移动，q用来指向当前节点的前一节点。用pm指针保存最小节点的前一节点，即每次把p更新给pm。外循环结束条件是循环链表空。内循环结束条件是q指向头结点。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #include<stack> using namespace std; // 链表节点结构 typedef struct Node{ int data; struct Node * next; Node(): next(NULL){}; Node(int data):data(data), next(NULL){}; }Node, *LinkList; // 输出循环单链表 void show(LinkList L){ Node * p = L->next; while(p != L){ cout<<p->data<<" "; p = p->next; } cout<<endl; } void deleteMin(LinkList &L){ while(L->next != L){ Node *p = L; Node *q = L->next; Node *pm = L; while(q!=L){ if(q->data < pm->next->data){ pm = p; } p = p->next; q = q->next; } Node * f = pm->next; pm->next = f->next; free(f); show(L); } free(L); } // 尾插创建链表 void careteListFromEnd(vector<int> v, LinkList &L){ // 创建头 L = new Node(); L->next = L; // 设置尾指针 Node *p = L; // 生成链表 for(int i : v){ Node *q = new Node(i); q->next = p->next; p->next = q; p = q; } } int main(){ int a[] = {3,2,1,4,5,0}; vector<int> va(a, a+6); int b[] = {7,8,9}; vector<int> vb(b, b+3); LinkList La, Lb; careteListFromEnd(va, La); careteListFromEnd(vb, Lb); deleteMin(La); return 0; }
