一亩三分地论坛

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

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

[树/链表/图] LinkedList

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-25 12:59:04 | 显示全部楼层 |阅读模式

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

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

x
我总是在LinkedList上的问题上有疑问,LinkedList一直是我的痛,感觉一直理解不过来哈。以下代码摘自网上,想问问,
1. 为啥要 ListNode leftDummy = new ListNode(0);                         而不是直接ListNode leftDummy;
2. 为啥要leftDummy 和 left
3.  这两句本质上我不是很清楚,如果能有图画出来似乎更好理解? left = head 啥意思?
left.next = head;
left = head;


题目在这: http://www.lintcode.com/en/problem/partition-list/

代码在这:
  1. public class Solution {
  2.     public ListNode partition(ListNode head, int x) {
  3.         if (head == null) {
  4.             return null;
  5.         }
  6.         
  7.         ListNode leftDummy = new ListNode(0);
  8.         ListNode rightDummy = new ListNode(0);
  9.         ListNode left = leftDummy, right = rightDummy;
  10.         
  11.         while (head != null) {
  12.             if (head.val < x) {
  13.                 left.next = head;
  14.                 left = head;
  15.             } else {
  16.                 right.next = head;
  17.                 right = head;
  18.             }
  19.             head = head.next;
  20.         }
  21.         
  22.         right.next = null;
  23.         left.next = rightDummy.next;
  24.         return leftDummy.next;
  25.     }
  26. }
复制代码
sharkwolf 发表于 2015-6-25 16:23:32 | 显示全部楼层
给楼主的建议,不符合或不爽请直接无视:
1、和学校、导师商量,quit PhD, 拿MS学位,去找工作,不要和人说读过CS 的Phd。
2、quit版主,自己悄悄地狠刷题;将之前的刷题贴删掉,如果我招人,看了你的贴,一点机会都不会给, 技能和behavior都不过。
回复 支持 5 反对 3

使用道具 举报

russianblue 发表于 2015-6-25 15:39:08 | 显示全部楼层
假定是用JAVA。
1. ListNode leftDummy = new ListNode(0);这个命令做了三件事情,一,等号左边新建一个名叫leftDummy的类型为ListNode的reference,位于stack上ListNode的method里面。二,new 命令会在heap上新建一个ListNode的Object,根据提供的constructor的signature,你需要一个argument作为val的值。三,你把leftDummy这个reference指向你建立的Object。你的替代方案只干了第一件事情,还需要做二和三。
2. leftDummy是一个新链表的起始点的reference,这个链表里面所有数小于x,而且生成时是按照原链表顺序的。left是在生成这个链表时不断移动的一个reference,每次生成一个以后left会移动到这个新链表的末尾。
3. 这个代码不太好的一点,用head指代正在移动的reference。简单说,left.next = head; 就是把现在新链表的末尾left指代的点的next这个reference指向head现在指向的那个点上。也就是新链表末尾又添了一个点。然后下一句left = head;把 left 这个reference本身指向head指向的那个点,也就是现在新链表的末尾的那个点。

需要指出的是,JAVA里的reference和c++/c的pointer是不一样的。在java里面,让两个reference相等,只是让它们指向同一个Object。而c里面让一个指针指向另一个指针会形成一个指针链。
3.

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

whoami250 发表于 2015-6-25 16:06:42 | 显示全部楼层
快毕业CS的PhD居然要靠Transportation的15fall PhD讲LinkedList,真是奇观
回复 支持 0 反对 1

使用道具 举报

zh355245849 发表于 2015-6-25 14:45:21 | 显示全部楼层
1. 前面是对象,创建了一个节点,后面的ListNode leftDummy;是对象引用,可以理解为指针;
2.一个对象,一个指针,利用指针操作的对象;
3.对象引用,理解为指针!  left.next = head; left的next指向head
                                        left=head; left指向head

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

whoami250 发表于 2015-6-25 16:07:10 | 显示全部楼层
russianblue 发表于 2015-6-25 15:39
假定是用JAVA。
1. ListNode leftDummy = new ListNode(0);这个命令做了三件事情,一,等号左边新建一个名 ...

赞一个   
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 16:27:43 | 显示全部楼层
zh355245849 发表于 2015-6-25 14:45
1. 前面是对象,创建了一个节点,后面的ListNode leftDummy;是对象引用,可以理解为指针;
2.一个对象,一 ...

感谢回答。

怪我第一个问题我没问清楚,我知道 ListNode leftDummy = new ListNode(0);   这行代码是创建一个新的对象, 但我的疑问是,构造方法里的参数为啥val 是 0 ,而不是其他的val, 比如1 呢 ? 赋0还是其他的有区别吗?已经看到好多赋0的了

第三个问题,
left.next = head;
left = head;
假设 head的val 是  10,(left.next = head;) left.next 是 left的下一个节点指向head, 即 left.next 的 val 是  10?
                               (left = head;) left 也指向head, 即  left 这个节点的val也是10?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 16:27:52 | 显示全部楼层
russianblue 发表于 2015-6-25 15:39
假定是用JAVA。
1. ListNode leftDummy = new ListNode(0);这个命令做了三件事情,一,等号左边新建一个名 ...

感谢回答。

怪我第一个问题我没问清楚,我知道 ListNode leftDummy = new ListNode(0);   这行代码是创建一个新的对象, 但我的疑问是,构造方法里的参数为啥val 是 0 ,而不是其他的val, 比如1 呢 ? 赋0还是其他的有区别吗?已经看到好多赋0的了

第三个问题,
left.next = head;
left = head;
假设 head的val 是  10,(left.next = head;) left.next 是 left的下一个节点指向head, 即 left.next 的 val 是  10?
                               (left = head;) left 也指向head, 即  left 这个节点的val也是10?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 16:36:42 | 显示全部楼层
本帖最后由 love1point 于 2015-6-25 16:37 编辑
sharkwolf 发表于 2015-6-25 16:23
给楼主的建议,不符合或不爽请直接无视:
1、和学校、导师商量,quit PhD, 拿MS学位,去找工作,不要和人 ...

1. 我有疑问我问出来不行吗?我问了,后来我懂了,是我自己知识层面上得到了收获。 phd or phd,does not relate to anything, does not mean anything, ok?

2. 版主 or 版主 和我问问题, 问啥问题一点关系一点都没有,ok? 我有问题,就问,怎么了? 为什么你就非得 要求cs phd要任何基础的东西全都cover?

我的top priority是做题找工作,其他的我不会理会,你要鄙视就鄙视,I don't care, 这是我第一次回复你,也是最后一次。谢谢你的关心
回复 支持 反对

使用道具 举报

DamienPooh 发表于 2015-6-25 16:39:09 | 显示全部楼层
赋零也好赋别的值也好没什么区别,反正最后返回的列表里面也不会有这两个节点 - 你去赋个12345,甚至是你的生日19xxxxxx之类的都无所谓。
第三个问题,在第14行执行完毕之后可以这么理解,但只是这一次循环里它的val是10.
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 16:53:22 | 显示全部楼层
sharkwolf 发表于 2015-6-25 16:23
给楼主的建议,不符合或不爽请直接无视:
1、和学校、导师商量,quit PhD, 拿MS学位,去找工作,不要和人 ...

"将之前的刷题贴删掉,"

这句话我只想用一句话来回复,懦弱的人才会极力想掩盖自己的短处,内心强大者,无谓


“如果我招人,看了你的贴,一点机会都不会给, 技能和behavior都不过。”
这是你personally assume 你可以提供内推,but in fact, is it true?

这个论坛里有各种声音,但大部分还是大家互相帮忙的(我向大家请教问题,同时我也回答大家的疑问)。也有一部分像你一样zhuang bi的,但其实也不无所谓哈,我 个人 welcome 批评,还能帮我进步,还能帮我出名,我为啥不欢迎呢?

回复 支持 反对

使用道具 举报

russianblue 发表于 2015-6-25 17:10:56 | 显示全部楼层
love1point 发表于 2015-6-25 16:27
感谢回答。

怪我第一个问题我没问清楚,我知道 ListNode leftDummy = new ListNode(0);   这行代码是 ...

constructor里面具体赋值应该没啥关系。只要是整数就行。用0便于和其他链表里面的数区别吧。(猜测)
准确的说,java里面reference指向object。left.next=head 不会让left.next的reference指向head这个reference。第一句执行时,left指向的是一个点(object1),left.next和head指向下一个点(object2),这个object2的val值为10.第二句把left也指向这个点,现在left和head指向同一个点(object2)了。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 17:30:04 | 显示全部楼层
russianblue 发表于 2015-6-25 17:10
constructor里面具体赋值应该没啥关系。只要是整数就行。用0便于和其他链表里面的数区别吧。(猜测)
准 ...

非常感谢。我受益匪浅
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 17:45:12 | 显示全部楼层
DamienPooh 发表于 2015-6-25 16:39
赋零也好赋别的值也好没什么区别,反正最后返回的列表里面也不会有这两个节点 - 你去赋个12345,甚至是你的 ...

好的,感谢回答哈,谢谢
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 21:47:29 | 显示全部楼层
谁能给我个链接(材料)能覆盖我的疑问呢,这一块我老是有问题,一直没解决
回复 支持 反对

使用道具 举报

sharkwolf 发表于 2015-6-25 23:01:22 | 显示全部楼层
love1point 发表于 2015-6-25 16:53
"将之前的刷题贴删掉,"

这句话我只想用一句话来回复,懦弱的人才会极力想掩盖自己的短处,内心强大者 ...

我在帮你! 看不出来?! 你可以不接受,我吃饱撑的!英文和中文混杂的用,可以接受,也是流行风格, 再混杂汉语拼音就low了,还用拼音吐脏口,看在你目前状态的份上,我就不投诉你了,好自为之。 祝内心强大的 CS PhD早日毕业,也祝能找到工作!
回复 支持 反对

使用道具 举报

sharkwolf 发表于 2015-6-25 23:15:11 | 显示全部楼层
love1point 发表于 2015-6-25 16:36
1. 我有疑问我问出来不行吗?我问了,后来我懂了,是我自己知识层面上得到了收获。 phd or phd,does not ...

不好意思, 别激动,我看贴是从后向前看, 刚回了你后面的贴,现在看到这贴你说是你对我第一次,也是最后一次回复,我晕菜了,难道穿越了!  实际上,你以前也回过我的贴。我充分理解你的第一目标是刷题找工作, 替你着想,最后一次建议你:悄悄地,低调地,努力地去刷题;以你的情况research的job恐怕有难度,quit PhD,拿MS去找码农的工作;quit掉版主,删掉一些帖子。真替你捉急啊!
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-6-25 23:59:16 | 显示全部楼层
sharkwolf 发表于 2015-6-25 07:15
不好意思, 别激动,我看贴是从后向前看, 刚回了你后面的贴,现在看到这贴你说是你对我第一次,也是最后 ...

刚看到。。恭喜你获得了和我同样的大字报待遇。。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-27 18:30:43 | 显示全部楼层
Remove Nth Node From End of List:   https://leetcode.com/problems/remove-nth-node-from-end-of-list/

我的idea:  先算出链表长度,然后指针跑到要被删除节点的前一个节点,然后把要被删除节点的前一个节点的next 指向 要被删除节点的下一个。但有bug,就是这种[1], 1
有人感兴趣讨论一下吗?
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public ListNode removeNthFromEnd(ListNode head, int n) {
  11.         int length = 0;
  12.         ListNode p = head;
  13.         while(p != null)
  14.         {
  15.             length++;
  16.             p = p.next;
  17.         }
  18.         
  19.         p = head;
  20.         
  21.         for(int i = 0; i < length - n - 1; i++)
  22.         {
  23.             p = p.next;
  24.         }
  25.         p.next = p.next.next;
  26.         return head;
  27.     }
  28. }
复制代码
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-6-27 19:17:14 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-6-27 19:20 编辑

这题可以双指针,其中一个先行K步
也可以先算长度,再一口气跑过去。注意boundary cases,比如k > n,k = n, head = NULL之类的。
在链表题里,不检查空指针是失(zuo)误(si)。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 14:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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