按递增次序输出单链表中各结点的数据元素

问题描述：

给定一个带表头结点的单链表，设head为头指针，结点的结构为(data,  next)，data 为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。

问题解答：

算法思想：对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查找次小值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间，该算法的时间复杂度为O(n²)。

void Min_Delete(LinkList &head){
    //head是带头结点的单键表的头指针，本算法按递增顺序输出单链表
    while(head->next!=NULL) {  //循环到仅剩头结点
        pre=head;  //pre为元素最小值结点的前驱结点的指针
        p=pre->next;  //p为工作指针
        while (p->next!=NULL) {
            if(p->next->data<pre->next->data)
                pre=p;  //记住当前最小值结点的前驱
            p=p->next;
        }
        print(pre->next->data);  //输出元素最小值结点的数据
        u=pre->next;  //删除元素值最小的结点，释放结点空间
        pre->next=u->next;
        free(u);
    }//while
    free (head);  //释放头结点
}

若题设不限制数组辅助空间的使用，则可先将链表的数据复制在数组里，再用时间复杂度为O(nlog₂n)的排序算法进行排序，然后将数组元素输出，时间复杂度为O(nlog₂n)。