一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 772|回复: 18
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-7 01:44:28 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
2.4 Write code to partition a linked list around a value x, such that all nodes less than
x come before all nodes greater than or equal to x.

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


JamesJi 发表于 2015-4-7 21:30:36 | 显示全部楼层
【解题思路】
新建一个linked list,然后将原来的linked list扫一遍,把比x小的全部放在新list的head之前,比x大的全部放到新list的tail之后,最后返回新linked list的head即可
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://github.com/JamesJi9277/C ... inkedLists/2.4.java
【test case】
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-8 00:20:04 | 显示全部楼层
【解题思路】
pretty straight forward  
iterate the  original list  
if  the data  >=x  
      thenode.next = x.next  and  x.next= thenode
else
    thenode.next = x.next ,x.next = thenode
    x.data<=>thenode.data    , x = x.next;

the tricky part is   handle  muple x  value node
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/06c8474a464686ac1643
【test case】
https://gist.github.com/michaelniu/06c8474a464686ac1643(main)
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-10 08:44:00 | 显示全部楼层
【解题思路】Create three new linked list using existing nodes, one contains all elements that are smaller than x, one contains all elements that are equals to x, then the last one contains all elements that are larger than x.
After we construct those three lists, we combine them together to get the result.
【时间复杂度】O(n)
【空间复杂度】O(1) // No extra memory
【gist link] https://github.com/bxshi/intervi ... ion_linked_list.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/2_4_test.cpp
回复 支持 反对

使用道具 举报

donghao 发表于 2015-4-10 10:24:26 | 显示全部楼层
JamesJi 发表于 2015-4-7 21:30
【解题思路】
新建一个linked list,然后将原来的linked list扫一遍,把比x小的全部放在新list的head之前 ...

请问,你的方法2中,为什么最后要做一个截断
我没做截断,总是会多输出一个,想不明白,求解答,谢谢
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-10 22:24:36 | 显示全部楼层
donghao 发表于 2015-4-9 21:24
请问,你的方法2中,为什么最后要做一个截断
我没做截断,总是会多输出一个,想不明白,求解答,谢谢

因为截断后就相当于linkedlist结束了呀
回复 支持 反对

使用道具 举报

donghao 发表于 2015-4-10 22:27:35 | 显示全部楼层
谢谢,我用了截断后做出了,你的意思就是新产生的llinklist 也要把最后node.next 为空
谢谢了,大神,每次写完,看你的算法,感觉自己弱爆了
回复 支持 反对

使用道具 举报

donghao 发表于 2015-4-10 22:27:41 | 显示全部楼层
谢谢,我用了截断后做出了,你的意思就是新产生的llinklist 也要把最后node.next 为空
谢谢了,大神,每次写完,看你的算法,感觉自己弱爆了
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-11 04:25:43 | 显示全部楼层
【解题思路】
存储原链表头给新指针,然后从链表头下一个节点开始遍历原链表,如果发现比数值小的,删除并添加进新增的链表,遍历结束后连接原链表和新增链表,最后比较表头的值,小则什么都不做,大则删除并添置末尾(是的我想的太复杂了...)
【时间复杂度】
O(n)
【空间复杂度】
O(1)/只多增加了三个节点
【gist link】
https://gist.github.com/alikewmk ... 2-4-dividelist-java
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-11 05:19:57 | 显示全部楼层
laonong15 发表于 2015-4-7 11:20
【解题思路】
pretty straight forward  
iterate the  original list  

is there any common way for design text cases?
回复 支持 反对

使用道具 举报

干.什么 发表于 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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 12:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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