s********e
发帖数: 243 | 1 how to reverse a linked list, using the most efficient way?
有没有牛人知道，什么方法算是Most efficient way? |
b********n
发帖数: 609 | 2 3个pointer。
【在 s********e 的大作中提到】
: how to reverse a linked list, using the most efficient way?
: 有没有牛人知道，什么方法算是Most efficient way?
|
i**********e
发帖数: 1145 | 3 这题应该是单链表必备的题目之一。
可以用循环和递归两种解法。我觉得循环应该是最efficient了，因为不用额外的stack
空间，而且也比较容易认证。递归的解法没那么直接，但仔细想一想其实也不难，必须
搞懂。
http://www.ihas1337code.com/2010/04/reversing-linked-list-iteratively-and.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s********e 的大作中提到】
: how to reverse a linked list, using the most efficient way?
: 有没有牛人知道，什么方法算是Most efficient way?
|
s********e
发帖数: 243 | 4 Thanks a lot!
stack
【在 i**********e 的大作中提到】
: 这题应该是单链表必备的题目之一。
: 可以用循环和递归两种解法。我觉得循环应该是最efficient了，因为不用额外的stack
: 空间，而且也比较容易认证。递归的解法没那么直接，但仔细想一想其实也不难，必须
: 搞懂。
: http://www.ihas1337code.com/2010/04/reversing-linked-list-iteratively-and.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
h***n
发帖数: 276 | 5 1）构造一个新链表，初始化为NULL
2) 遍历给定链表的每个元素，遇到一个，就删除一个，然后从头加入新链表
3）重复2)，直到给定链表的元素删完为止
【在 s********e 的大作中提到】
: how to reverse a linked list, using the most efficient way?
: 有没有牛人知道，什么方法算是Most efficient way?
|
d**f
发帖数: 264 | 6 http://www.ihas1337code.com
哥们你这个链接太及时了, find an elements in a sorted 2D array.
我下午onsite, 就是这道题,可惜我没有先看到啊
折腾了很久也没有想到那个最优算法
最后被HM一语道破.
stack
【在 i**********e 的大作中提到】
: 这题应该是单链表必备的题目之一。
: 可以用循环和递归两种解法。我觉得循环应该是最efficient了，因为不用额外的stack
: 空间，而且也比较容易认证。递归的解法没那么直接，但仔细想一想其实也不难，必须
: 搞懂。
: http://www.ihas1337code.com/2010/04/reversing-linked-list-iteratively-and.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 7 你这个答案不够优化，因为：
1）必须构造新的链表，需要额外空间。
2）必须把每一个元素给de-allocate，然后再allocate memory，需要额外的时间。
最优解是不需要变动元素的内存位置，变动的只是指针。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h***n 的大作中提到】
: 1）构造一个新链表，初始化为NULL
: 2) 遍历给定链表的每个元素，遇到一个，就删除一个，然后从头加入新链表
: 3）重复2)，直到给定链表的元素删完为止
|
i**********e
发帖数: 1145 | 8 这有点遗憾了啊，不过还是要bless你能拿到offer。
这on-site是什么公司啊？
怎么感觉好像由HM来出题？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 d**f 的大作中提到】
: http://www.ihas1337code.com
: 哥们你这个链接太及时了, find an elements in a sorted 2D array.
: 我下午onsite, 就是这道题,可惜我没有先看到啊
: 折腾了很久也没有想到那个最优算法
: 最后被HM一语道破.
:
: stack
|
h***n
发帖数: 276 | 9 是概念上的新链表，又不分配空间
是从原来的链表挪元素到新的链表，不是拷贝了节点插入到新的链表，再删除再删除旧
链表的节点
还有，你这个广告行为太明显了巴
【在 i**********e 的大作中提到】
: 你这个答案不够优化，因为：
: 1）必须构造新的链表，需要额外空间。
: 2）必须把每一个元素给de-allocate，然后再allocate memory，需要额外的时间。
: 最优解是不需要变动元素的内存位置，变动的只是指针。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
z****n
发帖数: 1379 | 10 怎么说呢，我觉得过于强调coding的时空复杂度也是种误区
他的方法coding起来非常简洁漂亮，变动指针的方法要同时记录前一个节点和后一个节
点，写起来出bug几率大的多
实际中，如果时空都能满足要求，我觉得还是简洁易懂的code更好
面试中，要我就先写简洁的，如果面试官质疑时空复杂度，再写变动指针的
【在 i**********e 的大作中提到】
: 你这个答案不够优化，因为：
: 1）必须构造新的链表，需要额外空间。
: 2）必须把每一个元素给de-allocate，然后再allocate memory，需要额外的时间。
: 最优解是不需要变动元素的内存位置，变动的只是指针。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
n******h
发帖数: 50 | 11 你这么弄和直接用3指针reverse步骤是一样的。只不过理解不同罢了。
【在 h***n 的大作中提到】
: 是概念上的新链表，又不分配空间
: 是从原来的链表挪元素到新的链表，不是拷贝了节点插入到新的链表，再删除再删除旧
: 链表的节点
: 还有，你这个广告行为太明显了巴
|
t*****j
发帖数: 1105 | 12 还不如三指针的。毕竟把内存是挪地方了。
【在 n******h 的大作中提到】
: 你这么弄和直接用3指针reverse步骤是一样的。只不过理解不同罢了。
|
