在链表中找出值相加大于指定值的最小节点问题
有一个链表，每个节点都有一个值，现在要求返回一个新链表，这个新链表由前一个链表中的节点组成，且新链表中的所有节点的值加起来大于指定值n，同时要求新链表节点数最少，求比较快的算法
[解决办法]
排序，从大往小添加
[解决办法]
假设最多情况下需要 N 个结点即可满足要求
定义一个结构体类型,存放键值和原链表中结点地址
typedef struct{
KeyType key; //用于比较大小的键值
NodeType* preAddress; //记录原链表中结点的前趋结点地址
} MaxNode;
定义一个大小为N的MaxNode型数组A,用来记录找到的最大的N个值
并设变量Sum记下A中结点键值的和
第一遍扫描每找到一个结点,将结点用插入法排序插入A数组中,
删除数组中比当前结点小的结点,并修改Sum的值
当Sum值大于定值n时,停止
利用数组A,建立新链表
如果发现N个不行,再考虑2*N重新进行一遍扫描,依次类推
如果N容易确定,且不大的话,效率应该不错
[解决办法]
用bst岂不更快
[解决办法]
to llg84:
你用的也是排序方法呀（冒泡排序），效率不高，但是象你说的
”在大部分情况下，应该是存在单个节点或是很少的节点即可满足要求的“
如果这样的话，该算法的效率就比其他排序好（个人看法^-^)
[解决办法]
1、构建和大于n的链表 B：
循环：
在 A 中抽取都节点 a，如果 a>n 则直接返回单个节点 a，否则按升序插入到 B 中；
一直到 SUM(B) > n。
2、压缩链表 B：
循环：
对链表 B 的头节点 b（由于 B 升序，所以 b = MIN(B)），如果 SUM(B)-b > n，则从 B 中删除 b；
一直到 B 为空或不满足删除条件。
如果 COUNT(B) = 1，直接返回 B。
3、替换 B 成员：
循环：
在 A 中抽取都节点 a，如果 a>n 则直接返回单个节点 a，如果 a ≤ b（B 的头节点）则直接抛弃 a，否则：
循环：
如果 SUM(B)+a-b > n 则从 B 中删除 b；
一直到 B 为空或不满足删除条件。
将 a 按升序插入到 B 中；
一直到 A 为空。
因为对 A 只进行了一次遍历，而对 B 的长度不可能超过初次构建的长度 k，复杂度 O(k^2) 比直接的 O(n^2) 要小一些。
