一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.23-6.29 CareerCup 2.4

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-23 00:00:05 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去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】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。
qianhuang 发表于 2014-6-23 20:03:11 | 显示全部楼层
【解题思路】
use a pointer p, we guarantee the nodes in [head, p] must be smaller than x. Scan the whole linked list, if the node is smaller than x, insert it  after p, and update p.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/adb2f6c2fd73cdc1ff89
回复 支持 2 反对 0

使用道具 举报

chouclee 发表于 2014-6-23 14:50:04 | 显示全部楼层
【解题思路】创建3个临时的LinkedList lessThan, equal,largerThan,traverse original linkedList,add corresponding elements to 3 LinkedLists respectively.再将equal和largerThan 2个LinkedList append 到lessThan里面,返回 lessThan这个linkedlist
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/4a1c7b1d06af700a0b44
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-23 19:30:22 | 显示全部楼层
【解题思路】创建2个临时的LinkedList lessThan, equalandlargerThan,然后遍历,同时考虑lessthan为null的情况
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/14942a249a44fb36de0b
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-24 04:02:27 | 显示全部楼层
【解题思路】
创建2个临时的LinkedList less, notLess,然后遍历,然后合在一起
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/UncleGarden/c5b19fbe945b21a67846
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-24 04:02:50 | 显示全部楼层
【解题思路】
创建2个临时的LinkedList less, notLess,然后遍历,然后合在一起
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/UncleGarden/c5b19fbe945b21a67846
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-25 03:50:13 | 显示全部楼层
【解题思路】
two temp list headers less and noless, iterate the list and append the node to the corresponding list.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/c87a88857239e80785c8
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-25 09:53:50 | 显示全部楼层
【解题思路】
Two linked list:
left - all nodes less than x
right - all nodes larger than x

Three pointers track:
Head of left
Tail of left
Head of right

Then normal partition procedure

【时间复杂度】
O(N)

【空间复杂度】
O(1) if allowed to mutate the original list

【gist link】
https://gist.github.com/chrislukkk/3901005117455405cf09
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-25 13:48:46 | 显示全部楼层
【解题思路】创建2个临时的LinkedList lessThan, equalandlargerThan,然后遍历
【时间复杂度】
O(N)
【空间复杂度】O(n)
【gist link】https://gist.github.com/hilda8519/ddec0a1e20ac8074e79c
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-26 08:25:04 | 显示全部楼层
【解题思路】
I have three linkedlist, one for less, one for equal, one for greater, get all value from original linkedlist,
and save it to correspoding linkedlist, lastly connect these three linkedlist.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/habina/719d2ca521e7695311c9
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-27 04:49:11 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-27 06:42:40 | 显示全部楼层
【解题思路】
set 2 list, one of nodes less than x and another of nodes more or equal to x;
insert into the lists from their head
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/f0c185fa59129c3f74d4
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-27 09:27:38 | 显示全部楼层
【解题思路】
Go through the list, if we see a node whose value is smaller than x,
         * delete it and then insert it to the head of the list
【时间复杂度】
O(n)
【空间复杂度】
O(1) if we are allowed to mutate the original list
【gist link】
https://gist.github.com/XiaoxiaoLi/80318ea564c6ad527c8e
回复 支持 反对

使用道具 举报

RealityPC 发表于 2014-6-27 10:55:56 | 显示全部楼层
【解题思路】create two list, scan over the original list and store all less elements in one list and all greater elements in another list. combine the two list
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/pchong90/f91f6e2c522f28cacbd4
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-28 01:47:15 | 显示全部楼层
【解题思路】Traverse the list, separate the list into two part with the original nodes, then return them with a node array.
【时间复杂度】O(n)
【空间复杂度】O(1) use 3 extra Node to save the middle node, larger head, less header
【gist link】https://gist.github.com/bitcpf/f51b82718f54bddfae74
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-28 03:27:38 | 显示全部楼层
【解题思路】create two list for less than x and not less x, traverse the list
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/yokiy/e60fc4079f4b7f9d3443
回复 支持 反对

使用道具 举报

心焰 发表于 2014-6-28 04:03:46 | 显示全部楼层

【解题思路】
Try to make it done without using external space, then need to keep track of head,tail and current processing node.
1. suppose that do not know the tail, then need to traverse it one time
2. traverse the list , if a node is less than x, move it to the head, otherwise, move it to the tail
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】

补充内容 (2014-6-30 08:32):
https://github.com/FinalF/CarrerUp/blob/master/moveAroundX.java
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-28 05:51:06 | 显示全部楼层
【解题思路】If we are allowed to modify the original linkedlist, we can traverse the whole list and keep the larger nodes unchanged, move the smaller nodes to the front of the linkedlist.   If not,  create two extra linkedlists for smaller nodes and larger nodes and then combine them.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jyhjuzi/ecaa9bf88b5858fe1f13
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-28 07:36:19 | 显示全部楼层
【解题思路】Use two linked lists, less and greater, if a node is smaller than val, append it to less, if it's larger than val, append it to greater. Then append greater to less.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/c63425af7a01dee9e868
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-28 20:08:37 | 显示全部楼层
【解题思路】
Ues two linked list: Less and NotLess.
Then iterate the original list and add the nodes to the corresponding list
Return the Less.addAll(NotLess)
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/ccfc5431a6748e968bd2
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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