链表排序的两种方式

一、交换结点的数据域

有很多种方法，比如冒泡排序，选择排序等其他排序方法

struct Node *link_sort(struct Node *head)
{ 
   
	int value;
	struct Node *p = head;
	struct Node *q = NULL;

	while(p)
	{ 
   
		q = p->next;
		while(q)
		{ 
   
			if(p->data > q->data)
			{ 
   
				value = p->data;
				p->data = q->data;
				q->data = value;
			}
			q = q->next;
		}
		p = p->next;
	}

	return head;
}

二、断开链表，重新形成

方法

跟三指针法反转链表类似，也是要定义三个结构体指针。

第一步：
第一个指针用于找最小值
第二个指针用于指向最小值的前一个结点
第三个指针用于遍历链表

第二步：
让最小值从链表当中脱离出来

第三步：
然后再定义一个新的指针，用头插法把指向最小值的指针
形成新的链表，通过调整新链表结点的插入方法和在原链表找最值得到升序或降序的效果。

示例

struct Node *link_sort(struct Node *head)
{ 
   
	struct Node *p = NULL;
	struct Node *pMin = NULL;
	struct Node *pMin_prev = NULL;
	struct Node *newHead = NULL;

	while(head)
	{ 
   
		//找到一个最值结点后，重新操作，原链表的结点个数不断减少
		p = head;
		pMin = head;
		pMin_prev = NULL;

		//1、找最值，遍历原链表
		while(p->next)
		{ 
   
			if(pMin->data > p->next->data) //结点数据域比较
			{ 
   
				pMin_prev = p; //标记
				pMin = p->next;
			}
			p = p->next;
		}
		//2、将最值结点脱离出原链表
		if(pMin == head) //情况一，刚好最值就是头结点
		{ 
   
			head = head->next; //原链表头节点往后移
			pMin->next = NULL; //断开连接，同时防止它乱指
		}
		else
		{ 
   
			pMin_prev->next = pMin->next;//断开结点
			pMin->next = NULL;
		}
		//3、插法入新链表，两种情况
		if(newHead == NULL)
		{ 
   
			newHead = pMin;
		}
		else
		{ 
   
			//头插法
			pMin->next = newHead;
			newHead = pMin;
		}
	}
	
	return newHead;
}