原地修改算法

不使用额外存储空间且修改的next指针数最少的原地算法,如图片所示,一次操作下,应该直接将5,6,10三个节点都放到3和18之间,也就是说只要修改3到5和10到18这两根“指针”。
图片说明

    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode p, q, rst;
        ListNode preP  = null, preQ = null, sQ;
        if(list1 == null || list2 == null)
            return (list1 == null) ? list2 : list1;
        if(list1.val <= list2.val){
            p = list1;
            q = list2;
        }else{
            p = list2;
            q = list1;
        }
        rst = p;
        sQ = q;
        while(p != null && q != null){
            while(p != null && p.val <= q.val){
                preP = p;
                p = p.next;
            }
            if(p == null){    // list1 中剩下元素比 list2 中最小元素小
                preP.next = sQ;//list2 接在 list1 后面,返回
                break;
            }
            while(q != null && q.val < p.val){ // 找到 q 中的值大小介于 preP 和 P 之间的最长子序列右边界。左边界为 sQ
                preQ = q;
                q = q.next;
            }
            // sQ 到 preQ 之间的节点应该存放在 preP 和 p 之间,所以只要修改以下两根“指针”
            //同时移动 sQ 到新的 q 位置
            preP.next = sQ;
            preQ.next = p;
            sQ = q;
        }

        return rst;
    }
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务