1. 有一个带头节点的单链表L（至少有一个数据节点），设计一个算法使其元素递增有序排 列，要求算法的空间复杂度为O(1)。（提示：采用以建表和以查找为基础的算法设计思 路）

算法思路：

从链表的第二个节点开始，依次将每个节点插入到已经排好序的链表中。具体来说，对于每个节点，需要找到它在已经排好序的部分中的插入位置，然后将它插入进去。

为了保证空间复杂度为O(1)，我们不能使用任何辅助数据结构，如数组、栈、队列等。但是，在链表中，我们可以使用一些指针来帮助我们完成插入操作。

具体来说，我们需要维护三个指针：

prev：指向已经排好序的部分中最后一个小于或等于当前节点值的节点；
cur：指向当前节点；
next：指向当前节点的下一个节点。

我们从链表的第二个节点开始遍历，对于每个节点cur，执行以下步骤：

1. 首先保存cur的下一个节点next，以防止链表断裂。

2. 在已经排好序的部分中，找到cur应该插入的位置，即找到最后一个小于或等于cur的节点prev。

3. 将cur插入到prev和prev的下一个节点之间，即：prev->next = cur; cur->next = prev->next;

4. 将cur移动到下一个节点，即：cur = next;

5. 重复步骤1~4，直到遍历完整个链表。

最后，链表中的元素就是递增有序排列的了。

算法实现：

typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;

void insertSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode *prev, *cur, *next;
prev = head;
cur = prev->next;
while (cur != NULL) {
next = cur->next;
if (cur->val < prev->val) {
// 找到插入位置
prev = head;
while (prev->next->val < cur->val) {
prev = prev->next;
}
// 插入节点
cur->next = prev->next;
prev->next = cur;
} else {
// 不需要插入，继续向后遍历
prev = cur;
}
cur = next;
}
}

时间复杂度：O(n^2)。

空间复杂度：O(1)。