📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 15078| 回复: 14
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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 一问
推荐
stellari 2015-6-1 00:34:03 | 只看该作者
全局:
链表题中经常会遇到这样的问题:链表的第一个node,因为没有前驱节点,所以该node需要特殊处理,会导致额外的代码量。如果创建一个dummy,将其作为第一个node的前驱节点,这样链表中所有的node都可以也能够同样的逻辑来处理了。

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

使用道具 举报

推荐
MCwong 2015-6-1 03:20:18 | 只看该作者
全局:
oio14644 发表于 2015-6-1 03:10
十分感谢, 但是 head = dummy 这句代码是什么意思? 是说head 从dummy 开始吗? 他俩的关系究竟是什么? ...

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

使用道具 举报

推荐
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把头结点记录下来的意思。......我也很水,不知道意思表达清楚没有.....希望能抛砖引玉吧~~

评分

参与人数 1大米 +2 收起 理由
xiaoshai12 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
南方的狼 2015-6-1 00:32:40 | 只看该作者
全局:
是没什么事
可是你总得把头指针给记录下来啊
回复

使用道具 举报

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

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

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

使用道具 举报

🔗
 楼主| 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 (9.98 KB, 下载次数: 3)

images.jpeg

评分

参与人数 1大米 +2 收起 理由
xiaoshai12 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 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还是指向那个
这样理解对吧
谢谢你的解答
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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