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步骤是一样的。只不过理解不同罢了。
|