题目: 合并两个有序链表

分析

归并法

合并两个有序链表，类似归并排序中最后一步的归并操作，使用两个指针分别指向两个链表的头部。

将两个指针指向元素中较小的数据存入目标链表，

之后将较小数据所在的链表指针向右移动，继续比较。

直到其中一个链表循环结束，则将另一个链表剩余的元素追加到目标链表尾部。

题解

归并法

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){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        
        ListNode node = new ListNode(-1); 
        ListNode root = node;
        
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                node.next = list1;
                node = node.next;
                list1 = list1.next;
            }else{
                node.next = list2;
                node = node.next;
                list2 = list2.next;
            }
        }
        
        if(list1 == null){
            node.next = list2;
        }
        if (list2 == null){
            node.next = list1;
        }
        return root.next;
    }
}