题解 | #合并两个排序的链表#

合并两个排序的链表

http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

题目

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
图片说明

输入描述

给定两个单调递增的链表。

返回值描述

输出两个链表合成后仍满足非递减的性质的链表

示例

输入:{1,3,5},{2,4,6}
返回值:{1,2,3,4,5,6}

思路

第一种方法:用的是笨方法。首先定义了一个存放ListNode的队列。遍历两个链表,①若两个链表均为空,返回一个为空的结点,也可以直接返回null;②若list1或者list2其中一个为空,则只用单独遍历这个不为空的链表,将每个结点从队尾入队;③若list1和list2均不为空,则比较这两个链表的当前结点的大小,谁的当前结点比较小,哪一个结点就从队尾入队,直至两个链表均为空,其中有一种情况是一个链表遍历完为空了,但是另一个链表还有结点,判断这种情况,单独遍历还有结点的链表即可。这样得到的队列d存放的就是从小到大排列的每一个结点。但是注意:此时它们仅仅是结点,并没有连接起来,故需要让队列的结点从队头出队,currentNode.next = d.pollFirst();这样返回第一个结点就是本题的结果了。

第二种方法:下次补充,思考思考先。

代码

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        Deque<ListNode> d = new ArrayDeque<>();
        Deque<ListNode> d1 = new ArrayDeque<>();
        if(list1 ==null && list2 == null){
            return null;
        }else if(list1 == null && list2 != null){
            d.addLast(list2);
            list2 = list2.next;
        }else if(list1 != null && list2 == null){
            d.addLast(list1);
            list1 = list1.next;
        }else{
            while(list1 !=null && list2 != null){
                if(list1.val < list2.val){
                    d.addLast(list1);
                    list1 = list1.next;
                }else{
                    d.addLast(list2);
                    list2 = list2.next;
                }

                if(list1 == null && list2 != null){
                    d.addLast(list2);
                    list2 = list2.next;
                }else if(list1 != null && list2 == null){
                    d.addLast(list1);
                    list1 = list1.next;
                }
            }

        }

        ListNode node = d.pollFirst();
        d1.addLast(node);
        while(d.size() != 0){
            node.next = d.pollFirst();
            node = node.next;
        }
        return d1.pollFirst();
    }
}
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        Deque<ListNode> d = new ArrayDeque<>();
        Deque<ListNode> d1 = new ArrayDeque<>();
        /*if(list1 ==null && list2 == null){
            return null;
        }else if(list1 == null && list2 != null){
            d.addLast(list2);
            list2 = list2.next;
        }else if(list1 != null && list2 == null){
            d.addLast(list1);
            list1 = list1.next;
        }else{*/
        if(list1 == null && list2 == null){
            return null;
        }else if(list1 == null && list2 != null){
            return list2;
        }else if(list1 != null && list2 == null){
            return list1;
        }else{
             while(list1 !=null && list2 != null){
                if(list1.val < list2.val){
                    d.addLast(list1);
                    list1 = list1.next;
                }else{
                    d.addLast(list2);
                    list2 = list2.next;
                }

                if(list1 == null && list2 != null){
                    d.addLast(list2);
                    list2 = list2.next;
                }else if(list1 != null && list2 == null){
                    d.addLast(list1);
                    list1 = list1.next;
                }
            }
        }

        ListNode node = d.pollFirst();
        d1.addLast(node);
        while(d.size() != 0){
            node.next = d.pollFirst();
            node = node.next;
        }
        return d1.pollFirst();
    }
}
全部评论

相关推荐

07-15 00:33
江苏大学 Java
代码飞升:哈哈哈哈评论区三个打广告的
简历中的项目经历要怎么写
点赞 评论 收藏
分享
水墨不写bug:疑似没有上过大学
点赞 评论 收藏
分享
07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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