题解 | #无环单链表插值#

struct ListNode* makelist( int n )
{
    struct ListNode* p = ( struct ListNode* )malloc( sizeof(struct ListNode) );
    struct ListNode* head = p;
    head->next = NULL;
    
    for( int i = 0;i < n-1;i++ )
    {
        struct ListNode* new = ( struct ListNode* )malloc( sizeof(struct ListNode) );
        new->next = NULL;
        new->val = 0;
        head->next = new;
        head = new;
    }
    
    return  p;
}

struct ListNode* insert(int* A, int ALen, int val ) 
{
    struct ListNode* res = makelist( ALen);        //首先将数组A创建成链表
    
    struct ListNode* p = res;
    
    struct ListNode* head = ( struct ListNode* )malloc( sizeof(struct ListNode) );
    head->val = val;
    head->next = NULL;
    
    
    for( int i = 0;i < ALen;i++ )
    {
        p->val = *(A+i);
        p = p->next;
    }
    
    p = res;
    
    if( val <= res->val )        //val 不大于 链表的第一个数值
    {
        head->val = val;
        head->next = res;
        return head;
    }
    
    while( p )
    {
        if( p->next )            //还没有到达链表的结尾
        {
            if( p->val <= val && p->next->val >= val )
            {
                head->next = p->next;
                p->next = head;
                return res;
            }
        }
        else                //到链表结尾还没有出现比val大的数值，val是最大的
        {
            p->next = head;
            return res;
        }
        p = p->next;
    }
    
    
    return NULL;
    
}