插入结点操作：前插、后插时间复杂度：前插0(n）、后插0(1)pre+*（a）插人到P之前（必须知道p的前甄pre）L（b）插人到P之后（不须知道P的前驱16中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 16 中国科学技术大学 时间复杂度：前插O(n)、后插O(1) 插入结点操作 ：前插、后插
删除结点操作时间复杂度O(n）Dsuc17中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 17 中国科学技术大学 删除结点操作 时间复杂度O(n)
单链表的其它操作举例【例】逆序创建链表时间复杂度O(nbbaeA818中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 18 中国科学技术大学 【例】逆序创建链表 时间复杂度O(n) L ∧ e p d p c p b p b p ∧ 单链表的其它操作举例
逆置单链表时间复杂度0（n）*逆置线性链表a.19中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 19 中国科学技术大学 逆置单链表 时间复杂度O(n)* 逆置线性链表 s p L a1 a2 a3 a4 ∧ L ∧ p a1 ∧ s p a2 s p a3 s p a4
【例】以单链表表示线性表实现集合的并void union L( LinkList &La, LinkList &Lb )if (!La) (La = Lb;return;)对比算法2.1while（Lb){s = Lb; Lb = Lb->next:p = La;while（p&&p->data!=s->data）//查找pre = p; p =p->next;/whileif(p）delete s;//找到else { pre->next = s; s->next = NULL;} //插入// while}// union L时间复杂度O(mXn)320ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 20 中国科学技术大学 【例】以单链表表示线性表实现集合的并 * void union_L( LinkList &La, LinkList &Lb ) { if (!La) {La = Lb;return;} while ( Lb ) { s = Lb; Lb = Lb->next; p = La; while ( p && p->data != s ->data ) { //查找 pre = p; p = p->next; }//while if ( p ) delete s; //找到 else { pre->next = s; s->next = NULL;} //插入 }// while }// union_L 时间复杂度O(m×n) 对比算法2.1