合并两个有序链表

原题链接

使用的方法

• 递归：通过递归的方式比较两个链表的头节点，选择较小的节点作为合并后的链表的头节点，然后递归地合并剩余的节点。

解题思路

• 首先，检查两个链表是否为空。如果其中一个链表为空，直接返回另一个链表作为结果。
• 然后，比较两个链表的头节点的值。选择较小的节点作为合并后的链表的头节点。
• 接下来，递归地合并剩余的节点。对于较小的节点，将其 next 指针指向递归调用的结果，即合并剩余的节点。
• 最后，返回合并后的链表的头节点。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    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;
        }
    }
}