java-合并两个排序的链表

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
示例1
输入
{1,3,5},{2,4,6}
返回值
{1,2,3,4,5,6}
解题思路
这是一个很简单的链表题
当两个链表为空时，返回空链表
当两个链表均不为空，谁的当前元素小，将谁放入新的链表中，然后指针右移
当最后只有一个非空链表时，直接放在新链表的右侧

java代码实现 14ms 9892KB

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null && list2==null){
            return null;
        }
        ListNode mylist=new ListNode(0);
        ListNode now=mylist;
        while(list1!=null && list2!=null){
            int key;
            if(list1.val<=list2.val){
                key=list1.val;
                list1=list1.next;
            }else{
                key=list2.val;
                list2=list2.next;
            }
            ListNode node=new ListNode(key);
            now.next=node;
            now=now.next;
        }
        if(list1 != null) now.next=list1;
        if(list2 != null) now.next=list2;
        return mylist.next;
    }
}

在不创建节点时，也可以直接进行指针指针转换，但是性能一般 14ms 10012KB

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null && list2==null){
            return null;
        }
        ListNode mylist=new ListNode(0);
        ListNode now=mylist;
//         while(list1!=null && list2!=null){
//             int key;
//             if(list1.val<=list2.val){
//                 key=list1.val;
//                 list1=list1.next;
//             }else{
//                 key=list2.val;
//                 list2=list2.next;
//             }
//             ListNode node=new ListNode(key);
//             now.next=node;
//             now=now.next;
//         }
        while(list1!=null && list2!=null){
            int key;
            if(list1.val<=list2.val){
                now.next=list1;
                now=now.next;
                list1=list1.next;
            }else{
                now.next=list2;
                now=now.next;
                list2=list2.next;
            }
        }
        if(list1 != null) now.next=list1;
        if(list2 != null) now.next=list2;
        return mylist.next;
    }
}