📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: pure0909
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第四轮】4.6 - 4.12 Career Cup 2.4

🔗
干.什么 2015-4-12 03:27:38 | 只看该作者
全局:
【解题思路】
Maintain two dummy nodes to track the less than, greater to equals to sublists. Iterate over the given list once terminate, partition the less tail to the greater head.

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/anonymous/d14c45d2297acc35fc5c
【test case】
回复

使用道具 举报

🔗
coperdli 2015-4-12 14:04:09 | 只看该作者
全局:
思路:遍历整个链表,若当节点值大于等于x,则将该节点删除并插入到链表尾端(这样保证大的节点都放到了后面),存在的一个问题是:大的节点都放到链表后面后会出现死循环(因为后面的节点都是大于x的,按照上述操作就会不断的将其删除并插入到链表尾),目前想到的一个终止条件是最多只循环2*length(linked-list)次,因为循环这么多次后,肯定可以实现小的在前,大的在后的结果。
时间复杂度:外围循环O(n),循环内的插入和删除也是O(n),故而O(n^2),进一步改进的话:增加尾指针则插入为O(1),删除的话也可以在O(1)实现,这种情况下总的时间复杂度可以达到O(n)
空间复杂度:目前我的实现是O(n), 因为删除元素部分把元素释放了,插入时又得新建一个节点;  进一步改进的话:删除时不用释放节点,然后直接将其插入到尾端,这种情况下时间复杂度可以达到O(1)
code snippet & test case: https://gist.github.com/coperd/0557e0ba93c885049150
回复

使用道具 举报

🔗
outtime 2015-4-12 19:57:28 | 只看该作者
全局:
【解题思路】
use two dummy nodes for two new linkedlist, one is smaller than x, one is >= x, then merge them.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/seeeking/705c7f3d460a30f58d97
【test case】
回复

使用道具 举报

🔗
daphne_ying 2015-4-13 13:54:01 | 只看该作者
全局:

【解题思路】
Maintain two dummy nodes to track the less than sublist and greater than or equal to sublist. In the end, merge the two sublists.

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/kelly-us/7676cd5ed4cff60cadab
回复

使用道具 举报

🔗
A30041839 2015-4-13 21:52:11 | 只看该作者
全局:
[solution]
use the partition algorithm of quick sort, apply it on the linked list.
[time]
O(n)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/3104923cbc4e89d66596
回复

使用道具 举报

🔗
iker01 2015-4-14 09:32:33 | 只看该作者
全局:
【解题思路】
# use two dummy nodes to store the nodes which are smaller than the key value
# and the larger nodes
# concatenate the two linked lists by removing the dummy nodes
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/zhangjiang2013/dd4ab8c9edd70cc42670
回复

使用道具 举报

🔗
sevenwonder 2015-4-21 05:25:53 | 只看该作者
全局:
【解题思路】
扫一遍大的放到后面小于等于的不动,注意加限制循环完len长度后跳出循环。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/songpu2015617/0edc83a050898168f58b
回复

使用道具 举报

🔗
Godbless 2015-5-28 10:51:43 | 只看该作者
全局:
【解题思路】Use two linked lists. The first one to store nodes smaller than x, and
        the second one to store nodes larger or equal to x. Then merge these two lists.
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_4.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复

使用道具 举报

🔗
voiding 2015-5-31 06:42:48 | 只看该作者
全局:
【解题思路】Create two list, one stores all nodes smaller than x, the other stores all nodes equal to or greater than x.
After going through the original list, merge two lists. In order to avoid null situation, I created a dummy head node for both lists (the smaller and the larger).
      
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link]https://gist.github.com/mogutou1214/7e2bf9814af04a5db5f8
【test case】see the link above
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表