题解 | #无环单链表插值#
无环单链表插值
https://www.nowcoder.com/practice/3ccf07c4d7374cc685be4a3883708540
//首先将数组A创建成链表。然后对val 和 链表中的数据进行比较，需要注意的是val小于链表的第一个数据，以及val大于链表中的所有数据
{
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;
}
