（线性表）设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间） (1)确定在序列中比正整数x大的数有几个（相同的数只计算一次）； (2) 在单链表将比正整数x小的数按递减次序排列；

(1) 算法思路：
从头到尾遍历链表，如果当前节点的值比x大，则将计数器加1，并将x的值更新为当前节点的值。如果当前节点的值等于x，则跳过（相同的数只计算一次）。最终计数器的值即为比正整数x大的数有几个。

(1) 代码实现：

int countLarger(Node* head, int x){
int count = 0;
while(head != NULL){
if(head->data > x){
count++;
x = head->data;
}else if(head->data == x){
//相同的数只计算一次
}
head = head->next;
}
return count;
}

(2) 算法思路：
遍历链表，将比正整数x小的节点插入一个新的链表中，并保持递减次序。最后将新链表接到原链表的尾部。

(2) 代码实现：

void sortDecreasing(Node* head, int x){
Node* newHead = NULL; //新链表的头节点
while(head != NULL){
if(head->data < x){
Node* newNode = new Node(head->data);
if(newHead == NULL || newNode->data > newHead->data){
newNode->next = newHead;
newHead = newNode;
}else{
Node* p = newHead;
while(p->next != NULL && p->next->data > newNode->data){
p = p->next;
}
newNode->next = p->next;
p->next = newNode;
}
}
head = head->next;
}
//将新链表接到原链表的尾部
Node* p = newHead;
while(p->next != NULL){
p = p->next;
}
p->next = head->next;
head->next = newHead;
}