l***4
发帖数: 1788 | 1 题目很简单：
1. 给一个linked list, 求长度
2. 实现在linked list中append一个节点
3. 实现在linked list中prepend一个节点
4. 利用上面的函数，实现将一个数组变成linked list.
但是有一个follow up：
5. 要求提高4的性能。
在哪些方面能提高？4已经是线性复杂度了 |
b**********5
发帖数: 7881 | 2 我觉得时append和prepend同时来？
【在 l***4 的大作中提到】
: 题目很简单：
: 1. 给一个linked list, 求长度
: 2. 实现在linked list中append一个节点
: 3. 实现在linked list中prepend一个节点
: 4. 利用上面的函数，实现将一个数组变成linked list.
: 但是有一个follow up：
: 5. 要求提高4的性能。
: 在哪些方面能提高？4已经是线性复杂度了
|
t*****3
发帖数: 112 | 3 4要用1、2、3的函数，可能你之前的三个方法的性能有问题
【在 l***4 的大作中提到】
: 题目很简单：
: 1. 给一个linked list, 求长度
: 2. 实现在linked list中append一个节点
: 3. 实现在linked list中prepend一个节点
: 4. 利用上面的函数，实现将一个数组变成linked list.
: 但是有一个follow up：
: 5. 要求提高4的性能。
: 在哪些方面能提高？4已经是线性复杂度了
|
b**********5
发帖数: 7881 | 4 为什么要用1,2,3？ 傻逼点的话, 不就一个个append?
【在 t*****3 的大作中提到】
: 4要用1、2、3的函数，可能你之前的三个方法的性能有问题
|
p*u
发帖数: 2454 | 5 repost:
they might want u 2 use vector to construct this linked list:
1: a vector is cache friendly;
2. O(1) random access: append is O(1) too, not O(n);
【在 b**********5 的大作中提到】
: 为什么要用1,2,3？ 傻逼点的话, 不就一个个append?
|
l***4
发帖数: 1788 | 6 我能想到的是在链表类里面keep一个尾节点 这样append也是O1
同时prepend和append应该也可行
★ 发自iPhone App: ChineseWeb 1.0.2
【在 b**********5 的大作中提到】
: 为什么要用1,2,3？ 傻逼点的话, 不就一个个append?
|
l***4
发帖数: 1788 | 7 感谢分享
★ 发自iPhone App: ChineseWeb 1.0.2
【在 p*u 的大作中提到】
: repost:
: they might want u 2 use vector to construct this linked list:
: 1: a vector is cache friendly;
: 2. O(1) random access: append is O(1) too, not O(n);
|
