c++ - 维护排序的链接列表

我正在尝试创建和维护排序的链接列表。应该以列表保持排序的方式插入每个新元素。我已经可以编写代码，但对我的代码不太满意。

基本上，根据我有4个条件需要满足，在我尝试实现所有这些条件时，我认为我使代码更复杂了。

只想知道是否有人编码效率更高，是否可以在这里告诉我如何改进插入功能。这是我下面的工作代码以及注释中的条件。为了保持小巧，我还没有发布删除元素，销毁列表等功能。

#include <iostream>

    using namespace std;

    struct node{
        int _val;
        node* _next;
    };

    void printList(node **s){

        node *t = *s;
        while(t){
            cout << t->_val << endl;
            t = t->_next;
        }
    }

    void insertSortElement(node** s, int val){

        node* t = *s;
        if(t){
            if(t->_next == NULL || (t->_val > val)){
                node* p = new node();
                p->_val = val;
                if(t->_val > val){
                    //3. More than 1 element in the list but 1st element > val
                    p->_next = t;
                    *s = p;
                }
                else{
                    //2. Only 1 element in the list and < val
                    t->_next = p;
                }
            }
            else{
                //4. More than 1 element and 1st < val
                node* prev = 0;
                while(t){
                    if(t->_val > val)
                        break;
                    prev = t;
                    t = t->_next;
                }
                node* p = new node();
                p->_val = val;
                p->_next = t;
                prev->_next = p;
            }
        }
        else{

            //1. no element in the list
            node* p = new node();
            p->_val = val;
            p->_next = NULL;
            *s = p;
        }
    }

    int main(){
        struct node* s = 0 ;

        insertSortElement(&s,5);
        insertSortElement(&s,6);
        insertSortElement(&s,4);
        insertSortElement(&s,2);
        insertSortElement(&s,8);
        insertSortElement(&s,1);
        printList(&s);
    }

编辑:

找到了另一个实现，比我的实现简单得多，并且可以处理所有情况

void insertSorted(node**s , int val){
        node* current = *s;

                if(current == NULL || current->_val >= val){
                        node* p = new node();
                        p->_val = val;
                        p->_next = current;
                        *s = p;
                }
                else{

                        while(current->_next != NULL || current->_next->_val < val)
                                current = current->_next;

                        node*  p = new node();
                        p->_val = val;
                        p->_next = current->_next;
                        current->_next = p;
                }
}

最佳答案

一种更快的方法是使用二进制搜索来找到正确的插入位置。它被称为“跳过列表”。

您也可以使用santinels来避免检查first和last元素的特殊情况。