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

合并两个排序的链表

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();
    }
}
全部评论

相关推荐

机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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