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

[树/链表/图] java 关于链表中Dummy Node用法的问题

全局:

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

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

x
本帖最后由 macctown 于 2015-9-9 23:59 编辑


复制代码
public static ListNode partition(ListNode head, int x) {
        //corner case
            if(head == null){
                return head;
        }

        ListNode lDummy = new ListNode(Integer.MIN_VALUE);
        ListNode gDummy = new ListNode(Integer.MAX_VALUE);
        ListNode p0 = head, pl = lDummy, pg = gDummy;    //??

        //loop from the first node of given list to the last
        while(p0!=null){
             if(p0.val < x){
             //if its value less than target, then make it into the lessList
                                pl.next = p0;
                                pl = p0;       
                    }
            else{
              //if its value greater than or equals to target, then make it into the greaterList
                             pg.next = p0;
                             pg = p0;  
                  }
          p0 = p0.next;        //move the pointer towards
        }

        pg.next = null;                //make the greaterList ends with null
        pl.next = gDummy.next;        //??

        return lDummy.next;

    }


这个问题是lintcode里面的Partition List问题。代码里面画问号的地方是我不理解的,我能理解dummy node在链表中使得头结点问题处理更简单这个概念。但是这个里面,将lDummy赋值给pl,gDummy赋值给pg,最后为什么gDummy.next指向的是pg里面第一个元素,lDummy.next则指向的是pl第一个元素.
十分感谢!

上一篇:来一道概率题,大家感受一下
下一篇:论python狗的优越感
推荐
mnmunknown 2015-9-10 00:13:10 | 只看该作者
全局:
在这个程序里,head, lDummy和gDummy是分别指向原链表的表头,小于x的链表表头 还有 大于等于x的链表表头,这三个指针从头到尾是不动的,因为后面需要对他们进行操作。

p0, pl, pg 一开始指向的其实和上一段的三个指针一样的,具有一样的起点。建这三个变量的原因是因为他们需要沿着链表向下走,而单向链表是条单行线,往下走了,就回不来了。

所以每个链表的第一个节点有两个reference,一个用来向下走,一个用来走到底需要拼接链表的时候帮你找到头在哪。
回复

使用道具 举报

🔗
 楼主| macctown 2015-9-10 00:17:57 | 只看该作者
全局:
mnmunknown 发表于 2015-9-10 00:13
在这个程序里,head, lDummy和gDummy是分别指向原链表的表头,小于x的链表表头 还有 大于等于x的链表表头, ...

soga...貌似是明白了!恍然大悟的感觉,你看是不是这样:程序里的pl=p0和pg=p0其实就是把pl和pg指到别的方向了,lDummy和gDummy就只记录了第一次,也就是lessList和greaterList的头结点位置,而pl和pg就一直走下去了。
太感谢了!!!~

评分

参与人数 1大米 +10 收起 理由
mnmunknown + 10 没错~ 就是这样 :D

查看全部评分

回复

使用道具 举报

🔗
parkhunter 2015-11-2 04:03:41 | 只看该作者
全局:
mnmunknown 发表于 2015-9-10 00:13
在这个程序里,head, lDummy和gDummy是分别指向原链表的表头,小于x的链表表头 还有 大于等于x的链表表头, ...

原来是这样,这问题最近也是有点不明白,恍然大悟,谢谢
回复

使用道具 举报

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

本版积分规则

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