c********d
发帖数: 173 | 1 给定一个双向链表，只知道里面的元素是单调的，现在要做插入，并且要维护原来的单
调性。
写出这个插入函数(java/c++/c都可以) |
H***e
发帖数: 476 | 2 ?
【在 c********d 的大作中提到】
: 给定一个双向链表，只知道里面的元素是单调的，现在要做插入，并且要维护原来的单
: 调性。
: 写出这个插入函数(java/c++/c都可以)
|
c********d
发帖数: 173 | 3 哪里不清楚吗？
【在 H***e 的大作中提到】
: ?
|
g********e
发帖数: 118 | |
L***Q
发帖数: 508 | 5 应该就是让找到合适位置插入。从链表头开始找，直到合适的位置。需要考虑一些
special case，比如空链表插入，插入在头或者尾。
【在 c********d 的大作中提到】
: 哪里不清楚吗？
|
c********d
发帖数: 173 | 6 对
【在 g********e 的大作中提到】
: 单调就是sorted的意思吗？
|
e***s
发帖数: 799 | |
L***Q
发帖数: 508 | 8 有不是O（n）的么？
一个有序链表不知道长度，插入点可能在任何一个地方，我想不出有不是O(n)的呢
【在 e***s 的大作中提到】
: O(n)吗？
: 注意改变指针的顺序就可以了。
|
c********d
发帖数: 173 | 9 这题目不考虑complexity，只考写程序
【在 e***s 的大作中提到】
: O(n)吗？
: 注意改变指针的顺序就可以了。
|
h****n
发帖数: 1093 | 10 双向链表很好做吧
先比较指向的元素和要插入的元素，如果大了，则往左走，如果小了往右走，直到找到
合适的位置然后做插入，要注意保存前后指针以便做插入操作
时间复杂度为o（n），由于是链表，没法binary search达到logn的复杂度 |
c********d
发帖数: 173 | 11 写出来再说好做，呵呵
【在 h****n 的大作中提到】
: 双向链表很好做吧
: 先比较指向的元素和要插入的元素，如果大了，则往左走，如果小了往右走，直到找到
: 合适的位置然后做插入，要注意保存前后指针以便做插入操作
: 时间复杂度为o（n），由于是链表，没法binary search达到logn的复杂度
|
