单链表使其原始元素递增有序

朴灿烈づ我的快乐病毒、 2021-12-12 23:57 196阅读 0赞

问题描述：有一个带头结点的单链表L，设计一个算法使其元素递增有序。(空间复杂度要求为O(1))。

算法思想：解决本题的思想类似于直接插入排序的思想。先构成只含一个数据结点的有序单链表，然后依次遍历单链表L中剩下的结点。在有序单链表中插入时，需要依次遍历有序单链表，直到找到插入位置，使得插入后有序单链表仍然有序。每当完成一次操作，链表L中元素减1，有序表中元素加1，直到链表L为空时结束。所以本算法的时间复杂度为O(n2).

算法代码：

void sort(LinkList &L){
    	LNode *p, *pre;
    	LNode *s;
    	p = L->next;
    	s = p->next;     //s指向要进行操作的链表
    	p->next = NULL; // 构成一个只含一个数据结点的有序表，初始时只有一个元素
    	while (s!=NULL)
    	{
    		p = s;   //p指向当前链表要进行操作的元素
    		s = s->next;  //s继续指向链表的下一个结点   
    		pre = L;
    		while (pre->next != NULL && pre->next->data <p->data)
    		{
    			pre = pre->next;      //在有序表中找到插入位置
    		}
    		p->next = pre->next;//在有序表的相应位置插入
    		pre->next = p;		
    	}
    }

完整代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    typedef char ElemType;
    typedef struct LNode{
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    void create(LinkList &L){
    	ElemType data;
    	LinkList s,p;
    	L = (LinkList)malloc(sizeof(LNode));
    	p = L;
    	cin >> data;
    	while (data!='#')
    	{
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = data;
    		p->next = s;//尾插法建立链表
    		p = s;
    		cin >> data;
    	}
    	p->next = NULL;
    }
    void sort(LinkList &L){
    	LNode *p, *pre;
    	LNode *s;
    	p = L->next;
    	s = p->next;     //s指向要进行操作的链表
    	p->next = NULL; // 构成一个只含一个数据结点的有序表，初始时只有一个元素
    	while (s!=NULL)
    	{
    		p = s;   //p指向当前链表要进行操作的元素
    		s = s->next;  //s继续指向链表的下一个结点   
    		pre = L;
    		while (pre->next != NULL && pre->next->data <p->data)
    		{
    			pre = pre->next;      //在有序表中找到插入位置
    		}
    		p->next = pre->next;//在有序表的相应位置插入
    		pre->next = p;		
    	}
    }
    int main(){
    	LinkList L;
    	cout << "输入链表元素(以#结束):";
    	create(L);
    	sort(L);
    	cout << "\n" << "链表调整后的结果：";
    	while (L->next!=NULL)
    	{
    		cout << L->next->data << "\t";
    		L = L->next;
    	}
    	system("pause");
    	return 0;
    }

运行结果：

![20190713004737114.png][]

[20190713004737114.png]: /images/20211210/fbb063aec21c41a1b3237f968b189e86.png