一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
macctown 发表于 2015-9-9 23:57:36 | 显示全部楼层 |阅读模式

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

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

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第一个元素.
十分感谢!
mnmunknown 发表于 2015-9-10 00:13:10 | 显示全部楼层
在这个程序里,head, lDummy和gDummy是分别指向原链表的表头,小于x的链表表头 还有 大于等于x的链表表头,这三个指针从头到尾是不动的,因为后面需要对他们进行操作。

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

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

使用道具 举报

 楼主| 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

查看全部评分

回复 支持 反对

使用道具 举报

parkhunter 发表于 2015-11-2 04:03:41 | 显示全部楼层
mnmunknown 发表于 2015-9-10 00:13
在这个程序里,head, lDummy和gDummy是分别指向原链表的表头,小于x的链表表头 还有 大于等于x的链表表头, ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 01:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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