如何将一个的单链表转换为有序的单链表

将一个无序的单链表转换为有序的单链表通常需要遍历整个链表，并按照一定的排序规则插入到新的有序链表中。这里以升序排列为例：

1. 创建一个新的头节点，表示新链表的开始，设为`head`。
2. 创建一个指针`current`，初始指向头节点。
3. 当原始链表非空时，进行循环：
a. 从原始链表获取当前元素，设为`temp`。
b. 比较`temp`的值与`current`所指向元素的值。如果`temp`较小，则将`temp`链接到`current`之后，然后更新`current`为`temp`，继续比较下一个元素；如果`temp`较大或相等，说明已经找到合适的位置，直接跳过`temp`。
4. 循环结束后，`current`所指向的就是新链表的最后一个节点，所以原始链表的尾部就是新链表的尾部。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* sortedListToSortedList(ListNode* head) {
    if (!head || !head->next) return head; // 如果链表为空或只有一个元素，已经是有序的
    ListNode dummy(0); // 新链表的头节点，用于简化操作
    dummy.next = head;
    
    ListNode *prev = &dummy, *cur = head;
    while (cur) {
        ListNode *next_temp = cur->next;
        while (next_temp && next_temp->val < cur->val) {
            prev->next = next_temp;
            prev = next_temp;
            next_temp = next_temp->next;
        }
        prev->next = cur;
        prev = cur;
        cur = next_temp;
    }
    
    return dummy.next; // 返回新链表的头节点
}