描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0 <= n <= 1000， -1000 <= 节点值 < = 1000

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}

类似地：在K个有序数组中，找出最小的N个值

思路1

比较两个链表的首节点，取出小的放到新链表中，直到两个链表为空

public class Solution {
    public ListNode Merge(ListNode list1, istNode list2) {
        //设置哨兵节点
        ListNode newNode = new ListNode(0);
        ListNode cur = newNode;
        //两个链表都不为空时，比较各自的首节点，添加到新链表中，指针移动
        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 newNode.next;
    }
}