一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-6-1 00:16:38 | 显示全部楼层 |阅读模式

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

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

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;
         }
}
MCwong 发表于 2015-6-1 03:20:18 | 显示全部楼层
oio14644 发表于 2015-6-1 03:10
十分感谢, 但是 head = dummy 这句代码是什么意思? 是说head 从dummy 开始吗? 他俩的关系究竟是什么? ...

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

使用道具 举报

南方的狼 发表于 2015-6-1 00:32:40 | 显示全部楼层
是没什么事
可是你总得把头指针给记录下来啊
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-1 00:34:03 | 显示全部楼层
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外的代码量。如果创建一个dummy,将其作为第一个node的前驱节点,这样链表中所有的node都可以也能够同样的逻辑来处理了。

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

使用道具 举报

 楼主| oio14644 发表于 2015-6-1 00:47:15 | 显示全部楼层
stellari 发表于 2015-6-1 00:34
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外 ...

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

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

使用道具 举报

avii 发表于 2015-6-1 01:56:15 | 显示全部楼层
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把头结点记录下来的意思。......我也很水,不知道意思表达清楚没有.....希望能抛砖引玉吧~~
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2015-6-1 02:00:49 | 显示全部楼层
avii 发表于 2015-6-1 01:56
楼主,我也纠结过跟你一样的问题觉得诶,没dummy什么事啊好像。后来我是这么理解的:这个程序里 ...

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

使用道具 举报

MCwong 发表于 2015-6-1 03:01:59 | 显示全部楼层
本帖最后由 MCwong 于 2015-6-1 03:03 编辑

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

使用道具 举报

 楼主| oio14644 发表于 2015-6-1 03:10:05 | 显示全部楼层
MCwong 发表于 2015-6-1 03:01
dummy始终记录的是合并后链表头的前驱节点,是静态的。而head记录的是合并过程中最新merge进来的节点, 是动 ...

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

使用道具 举报

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

使用道具 举报

JamesJi 发表于 2015-6-1 22:45:00 | 显示全部楼层
stellari 发表于 2015-5-31 11:34
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外 ...

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

使用道具 举报

木头人 发表于 2015-6-2 01:53:59 | 显示全部楼层
我觉得这个题就是说 dummy是头 然后head是用来指向头的 然后head=head.next类似于一次次把值加进去所以最后就返回dummy了
回复 支持 反对

使用道具 举报

Jocelyn000 发表于 2015-7-22 03:16:15 | 显示全部楼层
lz后来搞明白了吗。。。最近也在纠结这个问题。。。。
回复 支持 反对

使用道具 举报

foxone 发表于 2015-7-25 19:11:50 | 显示全部楼层
反正我的理解就是有了dummy node之后,你不用每次都去判断head是否为空,这对于很多链表题目来说带来了方便
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 02:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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