c++ - 维护排序链表

Question

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

根据我的说法，基本上有 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;
                }
}

Answer 1

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

您还可以使用 santinels 来避免检查第一个和最后一个元素的特殊情况。