有序链表：
按关键值排序。
删除链头时，就删除最小(/最大)的值，插入时，搜索插入的位置。
插入时须要比較O(N)，平均O(N/2)，删除最小(/最大)的在链头的数据时效率为O(1),
假设一个应用须要频繁的存取(插入/查找/删除)最小(/最大)的数据项，那么有序链表是一个不错的选择
优先级队列 能够使用有序链表来实现
有序链表的插入排序：
对一个无序数组，用有序链表来排序，比較的时间级还是O(N^2)
复制时间级为O(2*N)，由于复制的次数较少，第一次放进链表数据移动N次，再从链表拷贝到数组，又是N次
每插入一个新的链结点，不须要复制移动数据。仅仅须要改变一两个链结点的链域
import java.util.Arrays;
import java.util.Random;
/**
* 有序链表 对数组进行插入排序
* @author stone
*/
public class LinkedListInsertSort> {
private Link first;//首结点
public LinkedListInsertSort() {
}
public boolean isEmpty() {
return first == null;
}
public void sortList(T[] ary) {
if (ary == null) {
return;
}
//将数组元素插入进链表,以有序链表进行排序
for (T data : ary) {
insert(data);
}
//
}
public void insert(T data) {// 插入 到 链头, 以从小到大排序
Link newLink = new Link(data);
Link current = first, previous = null;
while (current != null && data.compareTo(current.data) > 0) {
previous = current;
current = current.next;
}
if (previous == null) {
first = newLink;
} else {
previous.next = newLink;
}
newLink.next = current;
}
public Link  deleteFirst() {//删除 链头
Link temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
public Link find(T t) {
Link find = first;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link delete(T t) {
if (isEmpty()) {
return null;
} else {
if (first.data.equals(t)) {
Link temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
}
Link p = first;
Link q = first;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (first-->last):");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link p = first, q = first.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == first) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1  pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里。把first.next 置空了, 而当q为null不运行循环时，p就为原来的最且一个数据项，反转后把p赋给first
first = p;
displayList();
}
class Link {//链结点
T data;//数据域
Link next; //后继指针，结点链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
LinkedListInsertSort list = new LinkedListInsertSort();
Random random = new Random();
int len = 5;
Integer[] ary = new Integer[len];
for (int i = 0; i < len; i++) {
ary[i] = random.nextInt(1000);
}
System.out.println("----排序前----");
System.out.println(Arrays.toString(ary));
System.out.println("----链表排序后----");
list.sortList(ary);
list.displayList();
}
}打印
----排序前----
[595, 725, 310, 702, 444]
----链表排序后----
List (first-->last):
the data is 310
the data is 444
the data is 595
the data is 702
the data is 725

题目：给定一个整数num，如何在节点有序的环形链表中插入一个节点值为num的节点，并保证这个环形链表依然有序。（假如链表是升序）
解决思路：

1.如果链表为空，则开辟一个节点，让后让他自己指向自己，然后返回该节点。

2.如果链表不为空，分为三种情况：

a.如果插入的节点的值是在环形链表最大值和最小的闭区间范围之内，即在链表[min,max]里面，那么先找到要插入的位置，然后插入。



b.如果插入的节点的值大于链表最后一个值，那么插入的位置就直接是最后一个节点的后面，然后让他指向头结点，最后返回头结点。



c.如果插入的节点小于链表的第一个节点，也就是小于最小的一个节点，那么插入的位置还是链表的最后一个节点的后面，然后让他指向头结点，最后返回新插入的节点。


有了方法，代码就比较好写了。
typedef struct node
{
	DataType data;
	struct node *p_next;
}Node ,*PNode;

PNode InsertInCircle(PNode head,DataType data)//插入一个节点在有序链表中，并且插入之后链表有序
{
	//1.如果环形链表是空，则将该节点插入，返回该节点
	if (head == NULL)
	{
		PNode pCur = NULL;
		pCur = (PNode)malloc(sizeof(Node));
		pCur->data = data;
		pCur->p_next = pCur;
		return pCur;
	}
	else
	{
		//2.先找到只要插入的位置
		pCur = head->p_next;
		PNode pPre = head;
		while (pCur != head)
		{
			//a.插入位置在链表内
			if (pPre->data <= data && pCur->data >= data)
			{
				PNode pNode = (PNode)malloc(sizeof(Node));
				pNode->data = data;
				pPre->p_next = pNode;
				pNode->p_next = pCur;
				return head;
			}
			pPre=pPre->p_next;
			pCur = pCur->p_next;
		}
		//.出循环,说明此时data是链表中最大或者是最小的节点
		//此时pCur==head
		PNode pNode = (PNode)malloc(sizeof(Node));
		pNode->data = data; 
		pPre->p_next = pNode;
		//b.比头结点小
		pNode->p_next = pCur;
		if (data < head->data)
			return pNode;
		else
			//比头结点大
			return head;
	}
}

结果：

测试的链表有5个节点，分别是1->2->3->4->5->1(最后的1是多打印了一次原链表只有一个值为1的节点）…

1.当链表为空



2.插入值为1的节点



3.插入值为2的节点



4.插入值为5的节点



5.插入值为6的节点


测试及源代码下载：源代码

实现代码

/*有序插入建立链表 C语言实现*/

#include<stdio.h>
#include<stdlib.h>

/*定义一个linklist结构体类型*/
typedef struct linklist
{
    int data;
    struct linklist *next;
}list, *plist;

/*按从小到大顺序插入*/
void order_insert_list(plist *head,int number)
{
    plist p_new = (plist)malloc(sizeof(list));
    plist pre = NULL;           /* pre指针作为temp指向next前的备份 */
    p_new->data = number;       /* 赋予新值给新结点 */
    p_new->next = NULL;         

    plist temp = (plist)malloc(sizeof(list));
    temp = *head;  /*每次插入前从链表头开始的位置*/

    /*首位空结点赋初值*/
    if (NULL == *head)
    {
        *head = p_new;
        return;
    }

    /*若新data比头结点小，头结点前插入*/
    if (p_new->data < temp->data)
    {
        p_new->next = temp; 
        *head = p_new;
        return;
    }
    else
    {
        while (NULL != temp)
        {   
            if (p_new->data >= temp->data)/* 新结点对当前结点data比较 */
            {
                pre = temp;     
                temp= temp->next;/*当前结点后移，直至5（比如1 2 3 5 插入4）的位置*/
                continue;
            }
            else
            {
                p_new->next = temp;/* 插入新结点 */
                pre->next = p_new; /* temp的前一个的位置的next指向新结点p_new */
                break;
            }           
        }
        if (NULL == temp)/* 当temp最终为尾结点时，说明新元素data最大，将结点作为尾结点 */
        {
            p_new->next = NULL;
            pre->next = p_new;   /* temp的前一个的位置的next指向新结点p_new */
        }
    }
}

void print_list(plist head)
{
    plist elem = head; 
    while (elem != NULL)
    {
        printf("%d ", elem->data);
        elem = elem->next;
    }
    printf("\n");
}

void main()
{
    int number;
    plist head;     /*定义表头*/
    head = NULL;

    printf("input some numbers:\n");
    scanf("%d", &number);
    while (number != -1) /*输入-1终止*/
    {
        order_insert_list(&head,number);
        scanf("%d", &number);
    }

    print_list(head);/*打印输出*/

    system("pause");
}

运行结果：

看到一道面试题：
typedef struct node
{
int 			value;
struct node*	next;
struct node*	prev;
} S_LIST_NODE;
//实现有序双向链表的插入和删除
int insert1(S_LIST_NODE* _list, int value);
int delete1(S_LIST_NODE* _list, int value);

删除我就不写了，正好回顾一下lambda的递归写法，如有不妥请评论直接指出。谢谢。
废话不多时上代码：
//有序双向链表
int insert1(S_LIST_NODE * _list, int value)
{
	node *temp = _list;
	function<void(node*)> lb = [&](node *_left)
	{
		if (_left==nullptr)
		{
			S_LIST_NODE *right = new S_LIST_NODE();
			right->value = value;
			right->prev = temp;
			right->next = nullptr;

			temp->next = right;
			return;
		}
		if (_left->value < value)
		{
			temp = _left;
			lb(_left->next);
		}
		else
		{
			S_LIST_NODE *left = new S_LIST_NODE();
			left->value = value;
			left->prev = temp;
			left->next = _left;

			temp->next = left;
			_left->prev = left;
		}
	};
	lb(temp->next);
	return 1;
}

调用方式:
	S_LIST_NODE * temp = new S_LIST_NODE();
	insert1(temp, 1);
	insert1(temp, 2);
	insert1(temp, 16);
	insert1(temp, 3);
	insert1(temp, 6);
	insert1(temp, 10);

递归lambda就需要使用是std::function保存lambda了。其他的没有什么特别之处，好久没写递归，还是思考了一晚上写出来的。有时间复习一下双递归的OJ赛题吧~~。