（算法）合并两个有序链表————＜递归＞

1. 题⽬链接：21.合并两个有序链表 

2. 题⽬描述：

3. 解法（递归）：

算法思路：

1. 递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；

2. 函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数 去处理；

3. 递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。

注意注意注意：链表的题⼀定要画图，搞清楚指针的操作！  

 C++算法代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    //对比两个链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        //为空时返回另一个链表
        if(list1==nullptr)
        {
            return list2;
        }
        if(list2==nullptr)
        {
            return list1;
        }
        //如果链表1的头结点<=链表2的头结点，链表1的后续节点在后续两个链表中比较取最小值
        if(list1->val<=list2->val)
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        //如果链表2的头结点<=链表1的头结点，链表2的后续节点在后续两个链表中比较取最小值
        else
        {
            list2->next=mergeTwoLists(list2->next,list1);
            return list2;
        }
    }
};

Java算法代码：

/**
 * 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 l1, ListNode l2) 
 {
 if(l1 == null) return l2;
 if(l2 == null) return l1;
 if(l1.val <= l2.val)
 {
 l1.next = mergeTwoLists(l1.next, l2);
 return l1;
 }
 else
 {
 l2.next = mergeTwoLists(l1, l2.next);
 return l2;
 }
 }
}