题目描述

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

输入

{1,3,5},{2,4,6}

返回值

{1,2,3,4,5,6}

思路分析

定义cur指向新链表的头节点（一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。）

1、如果list1指向的节点值小于list2指向的节点值，那么就将list1指向的节点值链接到cur的next指针，list1指向下一个节点。

2、否则，就将list2指向的节点值链接到cur的next指针，list2指向下一个节点。

3、重复1、2操作，直到list1为null或者list2为null。

4、最后将list1或者list2剩下的部分链接到cur的后面

核心代码

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        
        ListNode h = new ListNode(-1);
        ListNode cur = h;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1!=null) cur.next=list1;
        if(list2!=null) cur.next=list2;
        return h.next;
        
    }
}