由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 请问大牛们如何提高解决leetcode上面Linkedlist的题的能力？
相关主题
● 哪位大侠帮我看看这个code● Leetcode swap Paris 这个怎么改进？
● 各位刷友，leetcode里的题目：Copy List with Random Pointer● M家 onsite 悲剧，同胞们弄死烙印吧
● Leetcode新题 Copy List with Random Pointer● LeetCode:Partition List 哪位帮我看看， 为什么总是TLE
● 发个pure storage的interviewstreet题目● 请教大牛： Leetcode partition list: Time Limit Exceeded
● 合并两个排序好的链表, 优解?● Leetcode Copy List with Random Pointer Runtime Error?
● 弱问一个小问题，leetcode 上merge sorted list● leetcode Copy List with Random Pointer
● 问一个merge K sorted list的时间复杂度● copy list with random pointer 老出错
● 再问大牛们leetcode上面Linkedlist的题，Reverse Nodes in k-G● 求救！ Copy List With Random Pointer总是超时
相关话题的讨论汇总
话题: cur话题: next话题: null话题: listnode
进入JobHunting版参与讨论
1 (共1页)
a***e
发帖数: 413
1
这些题看着容易，老是写不对或者代码很冗长，有大牛们指点一下如何提高么？
呜呜，不知道哪年哪月才能刷完一遍，有同学互勉一下么？
比如
Given a linked list and a value x, partition it such that all nodes less
than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the
two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
我的
Runtime Error

Last executed input:
{1}, 0
ListNode *partition(ListNode *head, int x) {
if(head==NULL)
return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;

ListNode *cur = head->next;
ListNode *curHead = head;
ListNode *prev = head;
bool flag = false;
while(curHead!=NULL||cur!=NULL||prev!=NULL){
if ((cur->valval>x)){
cur = cur?cur->next:NULL;
curHead = curHead->next;
prev = prev->next;
}
else if (flag==false&&cur->val>=x){
flag=true;
prev = prev->next;
cur = cur?cur->next:NULL;
}
else if (flag==true&&cur->val prev->next = cur->next;
cur->next = curHead->next;
curHead->next = cur;
curHead = cur;
}
else{
cur = cur?cur->next:NULL;
curHead = curHead->next;
prev = prev->next;
}
}
return dummy->next;
}
看到别的答案，
ListNode* partition(ListNode* head, int x) {
ListNode left_dummy(-1); // 􀹨􀢲􀗄
ListNode right_dummy(-1); // 􀹨􀢲􀗄
auto left_cur = &left_dummy;
auto right_cur = &right_dummy;
for (ListNode *cur = head; cur; cur = cur->next) {
if (cur->val < x) {
left_cur->next = cur;
left_cur = cur;
} else {
right_cur->next = cur;
right_cur = cur;
}
}
left_cur->next = right_dummy.next;
right_cur->next = nullptr;
return left_dummy.next;
r*******k
发帖数: 1423
2
扫描一遍链表
整两个新链表
每个点跟x比，比x大放一个，小于放另一个
最后把这两个链表接起来就行了
记得要把拿出来的node的next置成null
否则容易有环

the

【在 a***e 的大作中提到】
: 这些题看着容易，老是写不对或者代码很冗长，有大牛们指点一下如何提高么？
: 呜呜，不知道哪年哪月才能刷完一遍，有同学互勉一下么？
: 比如
: Given a linked list and a value x, partition it such that all nodes less
: than x come before nodes greater than or equal to x.
: You should preserve the original relative order of the nodes in each of the
: two partitions.
: For example,
: Given 1->4->3->2->5->2 and x = 3,
: return 1->2->2->4->3->5.
M**a
发帖数: 848
3
已经刷完了。可是很多又忘了。
r*******k
发帖数: 1423
4
同感

【在 M**a 的大作中提到】
: 已经刷完了。可是很多又忘了。
h*******e
发帖数: 1377
5
这就达到张三丰教张无忌耍剑的境界了。

【在 M**a 的大作中提到】
: 已经刷完了。可是很多又忘了。
g*********5
发帖数: 1145
6
非常艰难的刷了20几道题，早忘了，更别提后面的没做过的了
a***n
发帖数: 623
7
链表题目就是考细心、考corner case、考指针来回穿插衔接的。静下心做就好。
y***n
发帖数: 1594
8
数据结构都还好，最搞的就是Array的题，变化太多，有时候很难想到好的答案。。
a***e
发帖数: 413
9
多谢各位，但现在试着在纸上跑程序，但有些就是搞不清哪里错了，比如这个
Copy List with Random Pointer
􀫭􀶍
A linked list is given such that each node contains an additional random
pointer which could point to
any node in the list or null.
Return a deep copy of the list.
􀙳􀼅
我看了idea，自己写了如下程序，但就是
Submission Result: Runtime Error
Last executed input:
{-1,#}
看了半天，试着一步一步走进去，还是不知道哪里错了，打算在VS里面debug一下看。
觉得和能通过的答案没有多少区别啊。。。。。。。。
My wrong answer.
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (head==NULL) return NULL;
RandomListNode *cur = head;
while(cur!=NULL){
RandomListNode *copied = new RandomListNode(cur->label);
copied->next = cur->next;
cur->next = copied;
cur = copied->next;
}
cur=head;

while(cur!=NULL){
if(cur->random!=NULL){
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
RandomListNode *newHead = head->next;
cur = newHead;
RandomListNode *oc = head;

while(cur){
oc->next = oc->next->next;
oc = oc->next;
if (cur->next){
cur->next = cur->next->next;
cur = cur->next;
}
}
return newHead;
}
};
Others' correct answer
for (RandomListNode* cur = head; cur != nullptr; ) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
for (RandomListNode* cur = head; cur != nullptr; ) {
if (cur->random != NULL)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
// 􀙳􀒷􀨆􀛱􀖆􀧽􀑖
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
return dummy.next;
a***e
发帖数: 413
10
多谢各位，但现在试着在纸上跑程序，但有些就是搞不清哪里错了，比如这个
Copy List with Random Pointer
􀫭􀶍
A linked list is given such that each node contains an additional random
pointer which could point to
any node in the list or null.
Return a deep copy of the list.
􀙳􀼅
我看了idea，自己写了如下程序，但就是
Submission Result: Runtime Error
Last executed input:
{-1,#}
看了半天，试着一步一步走进去，还是不知道哪里错了，打算在VS里面debug一下看。
觉得和能通过的答案没有多少区别啊。。。。。。。。
My wrong answer.
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (head==NULL) return NULL;
RandomListNode *cur = head;
while(cur!=NULL){
RandomListNode *copied = new RandomListNode(cur->label);
copied->next = cur->next;
cur->next = copied;
cur = copied->next;
}
cur=head;

while(cur!=NULL){
if(cur->random!=NULL){
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
RandomListNode *newHead = head->next;
cur = newHead;
RandomListNode *oc = head;

while(cur){
oc->next = oc->next->next;
oc = oc->next;
if (cur->next){
cur->next = cur->next->next;
cur = cur->next;
}
}
return newHead;
}
};
Others' correct answer
for (RandomListNode* cur = head; cur != nullptr; ) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
for (RandomListNode* cur = head; cur != nullptr; ) {
if (cur->random != NULL)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
// 􀙳􀒷􀨆􀛱􀖆􀧽􀑖
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
return dummy.next;
相关主题
● 弱问一个小问题，leetcode 上merge sorted list● Leetcode swap Paris 这个怎么改进？
● 问一个merge K sorted list的时间复杂度● M家 onsite 悲剧，同胞们弄死烙印吧
● 再问大牛们leetcode上面Linkedlist的题，Reverse Nodes in k-G● LeetCode:Partition List 哪位帮我看看， 为什么总是TLE
进入JobHunting版参与讨论
a***e
发帖数: 413
11
Ft, 用VS不到半分钟就发现问题。。。。。。。。。。。。
// while(cur){
while(cur&&oc){ //加这个check就行了
oc->next = oc->next->next;
oc = oc->next;
if (cur->next){
cur->next = cur->next->next;
cur = cur->next;
}
}
但这段程序就不用那么多check
// 􀙳􀒷􀨆􀛱􀖆􀧽􀑖
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
i*****t
发帖数: 68
12
画图，dummy头指针很handy，大多数用recursion和双指针
p*******u
发帖数: 949
13
翻来覆去刷
m******3
发帖数: 346
14
runtime error一般都是访问了不该访问的memory,比如数组越界，指针访问错误， 你
自己把程序拿出来在自己机器上跑跑看

【在 a***e 的大作中提到】
: 多谢各位，但现在试着在纸上跑程序，但有些就是搞不清哪里错了，比如这个
: Copy List with Random Pointer
: 􀫭􀶍
: A linked list is given such that each node contains an additional random
: pointer which could point to
: any node in the list or null.
: Return a deep copy of the list.
: 􀙳􀼅
: 我看了idea，自己写了如下程序，但就是
: Submission Result: Runtime Error
l***i
发帖数: 1309
15
推荐Sedgewick的algorithm in C，看相应章节，理解他的写法就好了。
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 求救！ Copy List With Random Pointer总是超时● 合并两个排序好的链表, 优解?
● 一道挺简单的题给搞砸了● 弱问一个小问题，leetcode 上merge sorted list
● 问个reverse linked list● 问一个merge K sorted list的时间复杂度
● 弱问题，连反转链表都看不懂了● 再问大牛们leetcode上面Linkedlist的题，Reverse Nodes in k-G
● 哪位大侠帮我看看这个code● Leetcode swap Paris 这个怎么改进？
● 各位刷友，leetcode里的题目：Copy List with Random Pointer● M家 onsite 悲剧，同胞们弄死烙印吧
● Leetcode新题 Copy List with Random Pointer● LeetCode:Partition List 哪位帮我看看， 为什么总是TLE
● 发个pure storage的interviewstreet题目● 请教大牛： Leetcode partition list: Time Limit Exceeded
相关话题的讨论汇总
话题: cur话题: next话题: null话题: listnode

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑