我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

查看: 5191|回复: 13
收起左侧

[其他] java 链表里面dummy node 一问?谢谢

[复制链接] |试试Instant~ |关注本帖
我的人缘0
oio14644 发表于 2015-6-1 00:16:38 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

x
刚刚学习链表, 请问 head = dummy 是把dummy的值赋给 head吗? 还是其他含义?
为什么最后返回dummy.next 就是返回合并之后的整个链表?貌似 循环过程没dummy 啥
事?

private ListNode merge(ListNode head1, ListNode head2) {
         ListNode dummy = new ListNode(-1);
         ListNode head = dummy;
         while (head1 != null && head2 != null ) {
            if (head1.val < head2.val) {
                head.next = head1;
                head1 = head1.next;
            }else {
                head.next = head2;
                head2 = head2.next;
            }
            head = head.next;
            
        }
         if (head1 != null) {
                    head.next = head1;
                    }
         else {
                head.next = head2;
                }
        return dummy.next;
    }


public class ListNode {
    int val;
          ListNode next;
          ListNode(int x) {
              val = x;
              next = null;
         }
}

上一篇:Segment Tree 要准备吗?
下一篇:Linked List Cycle II 一问
我的人缘0
stellari 发表于 2015-6-1 00:34:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外的代码量。如果创建一个dummy,将其作为第一个node的前驱节点,这样链表中所有的node都可以也能够同样的逻辑来处理了。

这段代码中如果没有dummy,那么要确定合并后的新链表头到底是head1还是head2,就必须加一个额外判断。而有了dummy以后,则可以不用这个判断,因为不管是head1还是head2,只要是紧接在dummy后面的,肯定就是head1和head2中较小的那个,这个一定是合并后的链表头。
回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
MCwong 发表于 2015-6-1 03:20:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
oio14644 发表于 2015-6-1 03:10
十分感谢, 但是 head = dummy 这句代码是什么意思? 是说head 从dummy 开始吗? 他俩的关系究竟是什么? ...

就是赋值, 想象你拉拉链的过程,一开始是要对齐的,然后再往上拉对吧。 head = dummy 就可以理解为是那个对齐的过程。
Dummy.next不是返回整个链表,而是返回合并后链表的头节点。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
南方的狼 发表于 2015-6-1 00:32:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
是没什么事
可是你总得把头指针给记录下来啊
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| oio14644 发表于 2015-6-1 00:47:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-6-1 00:34
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外 ...

谢谢解答,请问 head = dummy 是把dummy的值赋给 head吗? 还是其他含义?

为什么运行完 循环之后,没有把 head 重新赋给dummy 然后返回,
dummy 和head 是什么关系,就这一点不太明白,请帮忙,谢谢
回复 支持 反对

使用道具 举报

我的人缘0
avii 发表于 2015-6-1 01:56:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
oio14644 发表于 2015-6-1 00:47
谢谢解答,请问 head = dummy 是把dummy的值赋给 head吗? 还是其他含义?

为什么运行完 循环之后,没 ...

楼主,我也纠结过跟你一样的问题觉得诶,没dummy什么事啊好像。后来我是这么理解的:这个程序里面head是不断在移动着的。head = dummy 这句之后,就意味着dummy成了新的head。接下来楼主看,后面循环里根据不同情况判断head1和head2的大小,head.next = head1 或者 head.next = head2, 实际上就是从dummy这个node开始的。这就是楼上的前辈说的,用dummy把头结点记录下来的意思。......我也很水,不知道意思表达清楚没有.....希望能抛砖引玉吧~~
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| oio14644 发表于 2015-6-1 02:00:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
avii 发表于 2015-6-1 01:56
楼主,我也纠结过跟你一样的问题觉得诶,没dummy什么事啊好像。后来我是这么理解的:这个程序里 ...

握爪,看来困惑的不止我一个,谢谢你
回复 支持 反对

使用道具 举报

我的人缘0
MCwong 发表于 2015-6-1 03:01:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 MCwong 于 2015-6-1 03:03 编辑

dummy始终记录的是合并后链表头的前驱节点,是静态的。而head记录的是合并过程中最新merge进来的节点, 是动态的。lz可以脑补一下拉链
images.jpeg
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| oio14644 发表于 2015-6-1 03:10:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
MCwong 发表于 2015-6-1 03:01
dummy始终记录的是合并后链表头的前驱节点,是静态的。而head记录的是合并过程中最新merge进来的节点, 是动 ...

十分感谢, 但是 head = dummy 这句代码是什么意思? 是说head 从dummy 开始吗? 他俩的关系究竟是什么? 为什么最后返回 dummy.next 就是整个链表? 谢谢
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| oio14644 发表于 2015-6-1 03:26:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 oio14644 于 2015-6-1 04:03 编辑
MCwong 发表于 2015-6-1 03:20
就是赋值, 想象你拉拉链的过程,一开始是要对齐的,然后再往上拉对吧。 head = dummy 就可以理解为是那个 ...
dummy = head就是现在dummy和head都指向那个-1
然后head就开始移动,dummy还是指向那个
这样理解对吧
谢谢你的解答
回复 支持 反对

使用道具 举报

我的人缘0
JamesJi 发表于 2015-6-1 22:45:00 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-5-31 11:34
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外 ...

赞一个·······
回复 支持 反对

使用道具 举报

我的人缘0
木头人 发表于 2015-6-2 01:53:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我觉得这个题就是说 dummy是头 然后head是用来指向头的 然后head=head.next类似于一次次把值加进去所以最后就返回dummy了
回复 支持 反对

使用道具 举报

我的人缘0
Jocelyn000 发表于 2015-7-22 03:16:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
lz后来搞明白了吗。。。最近也在纠结这个问题。。。。
回复 支持 反对

使用道具 举报

我的人缘0
foxone 发表于 2015-7-25 19:11:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
反正我的理解就是有了dummy node之后,你不用每次都去判断head是否为空,这对于很多链表题目来说带来了方便
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 11:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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