每日一题-合并两个有序链表-0720

题目

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

思路

1. 当其中一个链表为空的时候，直接返回另一个链表
2. 比较两个链表当前节点的值，小的那个当作链表头节点，next指针指向下一个smaller节点，递归结束后，返回链表头节点

代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if(list1 == null){
    
            return list2;
        }
        if(list2 == null){
    
            return list1;
        }
        if(list1.val < list2.val){
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }