题目

已知单链表L中的结点是按值非递减有序排列的,试写一算法将值为X的结点插入表L中,使得L仍然有序
写出算法

提问时间：2021-03-13

答案

s表示要插入的节点,假设s已被赋值.
L表示目的链表,且L.head仅为头指针,不存储信息
Node* q = L.head
Node* p = L.head->next
while( p != NULL ) {
if( s->value value ) // 找到了s该插入的位置,并且此时p,q已记录下要插入的位置
break
else
q = p
p = p->next
}
// 将s节点插入到q,p节点之间
s->next = p;
q->next = s;
画画图就出来了,不过不要漏考虑插入位置在表头或表尾的情况