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

题目

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

输入描述

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

返回值描述

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

示例

输入：{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();
    }
}