21. 合并两个有序链表

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例+提示.png

分析：这题跟合并两个有序数组相似，可以考虑采用归并排序思想

思路：

1. 首先排除其中一个链表为空的情况
2. 设虚拟头节点
3. 遍历两个链表直至其中一个链表为空

• 对比链表结点的值，较小的先添加

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        //0.处理边界条件
        if(list1==null) return list2;
        if(list2==null) return list1;

        //1.定义需要的数据结构
        ListNode dummyHead = new ListNode();
        ListNode curr = dummyHead;
        //两个链表都不为空就继续遍历
        while(list1 != null && list2 !=null) {
              //比较大小
              if(list1.val < list2.val) {
                 curr.next = list1;
                 curr = list1;
                 list1 = list1.next;
              }else {
                 curr.next = list2;
                 curr = list2;
                 list2 = list2.next;
              }
        }

        //任意其中一个链表遍历完了，那就把没遍历完的链表拼接上
        if(list1 == null) {
            curr.next = list2;
        }else {
            curr.next = list1;
        }

        return dummyHead.next;

    }
}